.NET 4.x Поиск самого бюджетного пути из одного города в другой - C#
Формулировка задачи:
Добрый день!
Пишу программу для поиска самого дешёвого пути из одного города в другой. На С++ есть готовый вариант, но там массив заполняется программно, а это меня не очень устраивает. Переписал на С#. Но тут возникла проблема: скажем у меня есть 3 города. Соответственно я ввожу расстояния:
1 -> 2, 1 -> 3;
2 -> 1, 2 -> 3;
3 -> 1, 3 -> 2.
При запросе расстояния из первой сроки, всё нормально выводит(кроме нумерации городов, её ещё не отредактировал).
А при запросе из второй и третьей строки пишет ошибку в строке
if (distance[var_for_start = in_start + 1] != int.MaxValue) (третья с конца)
Помогите пожалуйста разрешить проблему.
P.S.: прилагаю код С++ и C#
#include <iostream> #include <conio.h> #define number_of_cities 10 using namespace std; void search_path(int arr_of_cities[number_of_cities][number_of_cities], int st, int fin) { int distance[number_of_cities]; bool visited[number_of_cities]; int count; int index; int i; int u; int m = st + 1; for (i = 0; i < number_of_cities; i++) { distance[i] = INT_MAX; visited[i] = false; } distance[st] = 0; for (count = 0; count < number_of_cities - 1; count++) { int min = INT_MAX; for (i = 0; i < number_of_cities; i++) if (!visited[i] && distance[i] <= min) { min = distance[i]; index = i; } u = index; visited[u] = true; for (i = 0; i <number_of_cities; i++) if (!visited[i] && arr_of_cities[u][i] && distance[u] != INT_MAX && distance[u] + arr_of_cities[u][i] < distance[i]) distance[i] = distance[u] + arr_of_cities[u][i]; } cout<<"The path cost path between two cities:\n"; for (i = 0; i < number_of_cities; i++) if ((i+1 == fin) && (m == st + 1)) if (distance[i] != INT_MAX) cout << m << " > "<< i+1 << " = " << distance[i] << endl; } int main() { setlocale(LC_ALL, "Rus"); int start; int finish; int arr_of_cities[number_of_cities][number_of_cities]= { {3, 1, 4, 11, 2, 3, 1, 4, 6, 8}, {1, 8, 9, 9, 4, 7, 2, 6, 8, 10}, {4, 3, 5, 7, 7, 5, 5, 8, 11, 3}, {5, 9, 7, 43, 3, 2, 7, 2, 4, 9}, {10, 8, 3, 12, 4, 8, 1, 7, 4, 14}, {6, 7, 9, 1, 0, 8, 6, 1, 8, 9}, {12, 15, 65, 12, 25, 13, 11, 24, 5, 7}, {15, 61, 7, 14, 14, 17, 16, 12, 25, 15}, {22, 13, 11, 19, 16, 15, 12, 15, 26, 14}, {21, 24, 16, 23, 31, 28, 19, 19, 16, 18}, }; cout << "Kyiv - 1; Kharkiv - 2; Donetsk - 3;" << endl << "Lviv - 4; Dnepropetrovsk - 5; Zaporozhye - 6;" << endl; cout << "Enter point of departure: "; cin >> start; cout << "Enter point of arrival: "; cin >> finish; if ((start < 0) ||(finish < 0) || (cin.get() != '\n')) cout << "You entered incorrect data. Try again" << endl; else if ((start > number_of_cities) || (finish > number_of_cities)) cout << "The route is not available " << endl; else search_path(arr_of_cities, start-1,finish); _getch(); return 0; }
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Project2 { class Program { static void Main(string[] args) { Console.WriteLine("Введите количество городов: "); int number = Convert.ToInt16(Console.ReadLine()); int[,] number_of_prices = new int[number, number]; string[] cities = new string[10000]; string str_start; string str_finish; int in_start = 0; int in_finish = 0; Console.WriteLine("Введите названия городов"); for (int i = 0; i < number; i++) { cities[i] = Convert.ToString(Console.ReadLine()); } for (int i = 0; i < number; i++) { Console.WriteLine("Введите цены соединения города "+cities[i]+":"); for (int j = 0; j < number; j++) { if (cities[i] == cities[j]) number_of_prices[i, j] = 0; else { Console.WriteLine("С городом " + cities[j]); number_of_prices[i, j] = Convert.ToInt16(Console.ReadLine()); } } } Console.WriteLine("Введите город отправления"); str_start = Convert.ToString(Console.ReadLine()); Console.WriteLine("Введите город пребытия"); str_finish = Convert.ToString(Console.ReadLine()); for (int i = 0; i < number; i++) { if (str_start == cities[i]) in_start = i + 1; if (str_finish == cities[i]) in_finish = i + 1; } ////////////////////////////////////////////////////////////////////////// int[] distance = new int[number]; bool[] visited = new bool[number]; int count = 0; int index = 0; int var_for_cycle = 0; int var_for_val = 0; int var_for_start = in_start + 1; for (var_for_cycle = 0; var_for_cycle < number; var_for_cycle++) { distance[var_for_cycle] = int.MaxValue; visited[var_for_cycle] = false; } distance[in_start - 1] = 0; for (count = 0; count < var_for_cycle - 1; count++) { int min = int.MaxValue; for (var_for_cycle = 0; var_for_cycle < number; var_for_cycle++) if ((!visited[var_for_cycle]) && distance[var_for_cycle] <= min) { min = distance[var_for_cycle]; index = var_for_cycle; } var_for_val = index; visited[var_for_val] = true; for (var_for_cycle = 0; var_for_cycle < number; var_for_cycle++) if (!visited[var_for_cycle] && distance[var_for_val] != int.MaxValue && (distance[var_for_val] + number_of_prices[var_for_val, var_for_cycle] < distance[var_for_cycle])) distance[var_for_cycle] = distance[var_for_val] + number_of_prices[var_for_val, var_for_cycle]; } for (var_for_cycle = 0; var_for_cycle < number; var_for_cycle++) if ((var_for_cycle + 1 == in_finish) && (var_for_start == in_start + 1)) if (distance[var_for_start = in_start + 1] != int.MaxValue) Console.WriteLine("Цена проезда из города " + var_for_start + " в город " + var_for_cycle + " равно: " + distance[var_for_cycle]); Console.ReadKey(); } } }
Решение задачи: «.NET 4.x Поиск самого бюджетного пути из одного города в другой»
textual
Листинг программы
for (var_for_cycle = 0; var_for_cycle < number; var_for_cycle++) if ((var_for_cycle + 1 == in_finish) && (var_for_start == in_start + 1)) if (distance[var_for_start = in_start + 1] != int.MaxValue)
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д