C # Программа для алгоритма кратчайшего пути Дейкстры | Жадный Алго-7

// AC # программа для сингла Дейкстры
// алгоритм поиска кратчайшего пути.
// Программа для матрицы смежности
// представление графика

using System;

class GFG {

    // Полезная функция для поиска

    // вершина с минимальным расстоянием

    // значение из множества вершин

    // еще не включены в кратчайшие

    // путь дерева

    static int V = 9;

    int minDistance(int[] dist,

                    bool[] sptSet)

    {

        // Инициализируем минимальное значение

        int min = int.MaxValue, min_index = -1;

        for (int v = 0; v < V; v++)

            if (sptSet[v] == false && dist[v] <= min) {

                min = dist[v];

                min_index = v;

            }

        return min_index;

    }

    // Утилита для печати

    // построенный массив расстояний

    void printSolution(int[] dist, int n)

    {

        Console.Write("Vertex     Distance "

                      + "from Source\n");

        for (int i = 0; i < V; i++)

            Console.Write(i + " \t\t " + dist[i] + "\n");

    }

    // Функция, которая реализует Дейкстру

    // алгоритм кратчайшего пути из одного источника

    // для графа, представленного с помощью смежности

    // матричное представление

    void dijkstra(int[, ] graph, int src)

    {

        int[] dist = new int[V]; // Выходной массив. расстояние [я]

        // будет держать самое короткое

        // расстояние от источника до меня

        // sptSet [i] будет истинным, если вершина

        // я включен в кратчайший путь

        // дерево или кратчайшее расстояние от

        // src to i завершен

        bool[] sptSet = new bool[V];

        // Инициализируем все расстояния как

        // INFINITE и stpSet [] как false

        for (int i = 0; i < V; i++) {

            dist[i] = int.MaxValue;

            sptSet[i] = false;

        }

        // Расстояние исходной вершины

        // от себя всегда 0

        dist[src] = 0;

        // Находим кратчайший путь для всех вершин

        for (int count = 0; count < V - 1; count++) {

            // Выбираем минимальную вершину расстояния

            // из множества вершин еще нет

            // обработанный. ты всегда равен

            // src в первой итерации.

            int u = minDistance(dist, sptSet);

            // Пометить выбранную вершину как обработанную

            sptSet[u] = true;

            // Обновляем значение dist соседнего

            // вершины выбранной вершины.

            for (int v = 0; v < V; v++)

                // Обновляем dist [v], только если не в

                // sptSet, есть край от тебя

                // к v, и общий вес пути

                // от src к v через u меньше

                // чем текущее значение dist [v]

                if (!sptSet[v] && graph[u, v] != 0 && 

                     dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])

                    dist[v] = dist[u] + graph[u, v];

        }

        // выводим построенный массив расстояний

        printSolution(dist, V);

    }

    // Код драйвера

    public static void Main()

    {

        / * Давайте создадим пример

график обсуждался выше *

        int[, ] graph = new int[, ] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

                                      { 4, 0, 8, 0, 0, 0, 0, 11, 0 },

                                      { 0, 8, 0, 7, 0, 4, 0, 0, 2 },

                                      { 0, 0, 7, 0, 9, 14, 0, 0, 0 },

                                      { 0, 0, 0, 9, 0, 10, 0, 0, 0 },

                                      { 0, 0, 4, 14, 10, 0, 2, 0, 0 },

                                      { 0, 0, 0, 0, 0, 2, 0, 1, 6 },

                                      { 8, 11, 0, 0, 0, 0, 1, 0, 7 },

                                      { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

        GFG t = new GFG();

        t.dijkstra(graph, 0);

    }

}

  
// Этот код предоставлен ChitraNayal