Рубрики

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

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

  
#include <limits.h>
#include <stdio.h>

  
// Количество вершин в графе
#define V 9

  
// Полезная функция для поиска вершины с минимальным значением расстояния, от
// набор вершин, еще не включенных в дерево кратчайших путей

int minDistance(int dist[], bool sptSet[])

{

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

    int min = INT_MAX, min_index;

  

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

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

            min = dist[v], min_index = v;

  

    return min_index;

}

  
// Утилита для печати построенного массива расстояний

int printSolution(int dist[], int n)

{

    printf("Vertex   Distance from Source\n");

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

        printf("%d tt %d\n", i, dist[i]);

}

  
// Функция, которая реализует алгоритм кратчайшего пути Дейкстры с одним источником
// для графа, представленного с использованием представления матрицы смежности

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

{

    int dist[V]; // Выходной массив. dist [i] будет содержать самый короткий

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

  

    bool sptSet[V]; // sptSet [i] будет истинным, если вершина i включена в кратчайший

    // дерево пути или кратчайшее расстояние от src до i завершено

  

    // Инициализируем все расстояния как INFINITE, а stpSet [] как false

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

        dist[i] = INT_MAX, sptSet[i] = false;

  

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

    dist[src] = 0;

  

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

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

        // Выбираем минимальное расстояние вершины из множества вершин, а не

        // еще не обработано. u всегда равен src в первой итерации.

        int u = minDistance(dist, sptSet);

  

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

        sptSet[u] = true;

  

        // Обновляем значение dist соседних вершин выбранной вершины.

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

  

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

            // u к v, а общий вес пути от src до v через u равен

            // меньше текущего значения dist [v]

            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX

                && dist[u] + graph[u][v] < dist[v])

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

    }

  

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

    printSolution(dist, V);

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    / * Давайте создадим примерный граф, обсужденный выше * /

    int graph[V][V] = { { 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 } };

  

    dijkstra(graph, 0);

  

    return 0;

}

Выход:

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

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

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

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

0.00 (0%) 0 votes