Поиск кратчайшего пути - C# (181681)
Формулировка задачи:
В одном массиве даны все возможные комбинации чисел (0,1,2,3,4). Представляют собой города.
В другом массиве - расстояния между этими городами.
Решение задачи: «Поиск кратчайшего пути»
textual
Листинг программы
class Program { public static double[,] ArrayDistance; static void Main(string[] args) { List<String> city=new List<string>(); String line = String.Empty; do { Console.Clear(); Console.WriteLine("В списке {0} городов, введите название города: ",city.Count); line = Console.ReadLine(); if(line!="") city.Add(line); } while (line!=""); if (city.Count < 3) { Console.Clear(); Console.WriteLine("В списке должно быть не менее трех городов!"); Console.ReadLine(); return; } ArrayDistance=new double[city.Count,city.Count]; ClearTo(ref ArrayDistance,-1); for (int i = 0; i < city.Count; i++) { ArrayDistance[i, i] = 0; } for (int i = 0; i < city.Count; i++) { for (int j = 0; j < city.Count; j++) { if (ArrayDistance[i, j] == -1) { try { Console.Clear(); Console.WriteLine("Введите расстояние между {0} и {1}:",city[i],city[j]); String dist = Console.ReadLine(); if (dist != null) { double distance = Double.Parse(dist); ArrayDistance[i, j] = distance; ArrayDistance[j, i] = distance; } } catch (Exception) { Console.Clear(); Console.WriteLine("Вы ввели не правильное число. Работа программы прекращена."); Console.ReadLine(); return; } } } } Console.Clear(); Console.WriteLine("Ниже приведен список городов: "); for (int i = 0; i < city.Count; i++) { Console.WriteLine("{0} - {1}",i,city[i]); } String count_route = (city.Count - 1).ToString(); Console.WriteLine("Выберите из какого города стартует маршрут (0-{0}) : ", count_route); String from_string = Console.ReadLine(); Console.WriteLine("Выберите в какой город просчитать маршрут (0-{0}) : ",(city.Count-1)); String to_string = Console.ReadLine(); int from = 0; int to = 0; try { from = Int32.Parse(from_string); to = Int32.Parse(to_string); if(from>(city.Count-1) && to>(city.Count-1)) throw new Exception(); if (from == to) { Console.Clear(); Console.WriteLine("Расстояние между городами 0км."); Console.ReadLine(); return; } } catch (Exception) { Console.Clear(); Console.WriteLine("Вы ввели не правильное число. Работа программы прекращена."); Console.ReadLine(); return; } Console.Clear(); Console.WriteLine("Поиск кратчайшего пути..."); double result=SearchShortWay(from,to,new List<int>()); Console.WriteLine("Растояние между {0} и {1} = {2}", city[from], city[to], result); Console.ReadLine(); } public static void ClearTo(ref double[,] array, int val) { for (int i = array.GetLowerBound(0); i <= array.GetUpperBound(0); i++) { for (int j = array.GetLowerBound(1); j <= array.GetUpperBound(1); j++) { array[i, j] = val; } } } public static double SearchShortWay(int index_from, int index_to, List<int> used_city) { double result = 0; List<double> shortway=new List<double>(); for (int i = 0; i < ArrayDistance.GetLength(0); i++) { bool flag = false; foreach (int index in used_city) { if (i == index) flag = true; } if(flag) continue; if(i==index_from) continue; //List<int> used_city_temp=new List<int>(); if (i != index_to) { double part_way=ArrayDistance[index_from, i]; used_city.Add(index_from); shortway.Add(part_way + SearchShortWay(i, index_to, used_city)); } else { shortway.Add(ArrayDistance[index_to,index_from]); } } result = shortway.Min(); return result; } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д