Найти для 1-го города кратчайшие пути в другие города - C#

Узнай цену своей работы

Формулировка задачи:

Есть некоторое количество городов, некоторые из которых соединены дорогами известной длины. Вся система дорог описывается квадратной матрицей порядка n, в которой элемент равен любом отрицательном числу, если город i непосредственно не соединен с городом j и равный длине дороги в противном случае. Найти для 1-го города кратчайшие пути в другие города. Входными данными считать количество городов и матрицу дорог.

Решение задачи: «Найти для 1-го города кратчайшие пути в другие города»

textual
Листинг программы
using System;
 
class Program
{
    //алгоритм Дейкстры
    static void Dijkstra(int[][] GR, int st)
    {
        int V = GR.GetLength(0);
        int count, index = 0, i, u, m = st + 1;
        int[] distance = new int[V];
        bool[] visited = new bool[V];
 
        for (i = 0; i < V; i++)
        {
            distance[i] = int.MaxValue; visited[i] = false;
        }
 
        distance[st] = 0;
 
        for (count = 0; count < V - 1; count++)
        {
            int min = int.MaxValue;
            for (i = 0; i < V; i++)
                if (!visited[i] && distance[i] <= min)
                {
                    min = distance[i]; index = i;
                }
            u = index;
            visited[u] = true;
            for (i = 0; i < V; i++)
                if (!visited[i] && GR[u][i] != 0 && distance[u] != int.MaxValue &&
                    distance[u] + GR[u][i] < distance[i])
                    distance[i] = distance[u] + GR[u][i];
        }
 
        Console.WriteLine("Стоимость пути из начальной вершины до остальных:\t\n");
        for (i = 0; i < V; i++) if (distance[i] != int.MaxValue)
                Console.WriteLine("{0} -> {1} = {2}", m, i + 1, distance[i]);
            else
                Console.WriteLine(@"{0} -> {1} = ""маршрут недоступен", m, i + 1);
    }
    //главная функция
    static void Main(string[] args)
    {
 
 
        int[][] GR = new int[6][] { 
        new int[] { 0, 1, 4, 0, 2, 0 }, 
        new int[] { 0, 0, 0, 9, 0, 0 }, 
        new int[] { 4, 0, 0, 7, 0, 0 }, 
        new int[] { 0, 9, 7, 0, 0, 2 }, 
        new int[] { 0, 0, 0, 0, 0, 8 }, 
        new int[] { 0, 0, 0, 0, 0, 0 } };
 
        Console.WriteLine("Начальная вершина >> ");
        int start = int.Parse(Console.ReadLine());
 
        Dijkstra(GR, start - 1);
    }
}

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


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

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

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