Поиск кратчайшего пути - 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;
        }
    }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

6   голосов , оценка 3.5 из 5
Похожие ответы