Рубрики

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

По заданному графу и исходной вершине в графе найдите кратчайшие пути от источника ко всем вершинам данного графа.

Алгоритм Дейкстры очень похож на алгоритм Прима для минимального остовного дерева . Как и MST Prim, мы генерируем SPT (дерево кратчайшего пути) с заданным источником в качестве root. Мы поддерживаем два набора, один набор содержит вершины, включенные в дерево кратчайшего пути, другой набор включает вершины, еще не включенные в дерево кратчайшего пути. На каждом шаге алгоритма мы находим вершину, которая находится в другом наборе (набор еще не включен) и имеет минимальное расстояние от источника.

Ниже приведены подробные шаги, используемые в алгоритме Дейкстры для нахождения кратчайшего пути от одной исходной вершины ко всем остальным вершинам данного графа.
Алгоритм
1) Создайте набор sptSet (набор дерева кратчайших путей), который отслеживает вершины, включенные в дерево кратчайших путей, т. Е. Минимальное расстояние от источника которого рассчитывается и завершается. Изначально этот набор пуст.
2) Назначьте значение расстояния для всех вершин входного графа. Инициализируйте все значения расстояния как БЕСКОНЕЧНЫЙ. Назначьте значение расстояния как 0 для исходной вершины, чтобы она выбиралась первой.
3) Хотя sptSet не включает в себя все вершины
…. a) Выберите вершину u, которой нет в sptSet и которая имеет минимальное значение расстояния.
…. б) Включите u в sptSet .
…. c) Обновить значение расстояния всех смежных вершин u. Чтобы обновить значения расстояния, выполните итерацию по всем смежным вершинам. Если для каждой смежной вершины v сумма значений расстояния u (от источника) и веса ребра uv меньше значения расстояния v, то обновите значение расстояния v.

C #

// 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

Выход:

Vertex     Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

Пожалуйста, обратитесь к полной статье об алгоритме кратчайшего пути Дейкстры | Жадный Алго-7 для более подробной информации!

Рекомендуемые посты:

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

0.00 (0%) 0 votes