Рубрики

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

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

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

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

Давайте разберемся со следующим примером:

Набор sptSet изначально пуст, а расстояния, назначенные вершинам, равны {0, INF, INF, INF, INF, INF, INF, INF, INF}, где INF указывает на бесконечность. Теперь выберите вершину с минимальным значением расстояния. Вершина 0 выбрана, включите ее в sptSet . Таким образом, sptSet становится {0}. После включения 0 в sptSet обновите значения расстояний смежных вершин. Смежные вершины 0 равны 1 и 7. Значения расстояний 1 и 7 обновляются как 4 и 8. В следующем подграфе показаны вершины и значения их расстояний, показаны только вершины с конечными значениями расстояний. Вершины, включенные в SPT, показаны зеленым цветом.

Выберите вершину с минимальным значением расстояния и еще не включенным в SPT (не в sptSET). Вершина 1 выбрана и добавлена в sptSet. Таким образом, sptSet теперь становится {0, 1}. Обновите значения расстояния смежных вершин 1. Значение расстояния вершины 2 становится 12.

Выберите вершину с минимальным значением расстояния и еще не включенным в SPT (не в sptSET). Вершина 7 выбрана. Таким образом, sptSet теперь становится {0, 1, 7}. Обновите значения расстояния смежных вершин 7. Значение расстояния вершин 6 и 8 становится конечным (15 и 9 соответственно).

Выберите вершину с минимальным значением расстояния и еще не включенным в SPT (не в sptSET). Вершина 6 выбрана. Таким образом, sptSet теперь становится {0, 1, 7, 6}. Обновите значения расстояния соседних вершин, равные 6. Значения расстояния вершин 5 и 8 будут обновлены.

Мы повторяем вышеупомянутые шаги, пока sptSet действительно не включает все вершины данного графа. Наконец, мы получаем следующее дерево кратчайших путей (SPT).

Как реализовать описанный выше алгоритм?

Мы используем логический массив sptSet [] для представления набора вершин, включенных в SPT. Если значение sptSet [v] равно true, то вершина v включается в SPT, в противном случае нет. Массив dist [] используется для хранения кратчайших значений расстояния всех вершин.

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[])

{

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

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

        printf("%d \t\t %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);

}

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

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;

}

Джава

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

import java.util.*;

import java.lang.*;

import java.io.*;

  

class ShortestPath {

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

    // из множества вершин, еще не включенных в дерево кратчайших путей

    static final int V = 9;

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

    {

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

        int min = Integer.MAX_VALUE, 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[])

    {

        System.out.println("Vertex \t\t Distance from Source");

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

            System.out.println(i + " \t\t " + dist[i]);

    }

  

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

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

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

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

    {

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

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

  

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

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

        Boolean sptSet[] = new Boolean[V];

  

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

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

            dist[i] = Integer.MAX_VALUE;

            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, есть

                // ребро от u до v и общий вес пути от src до

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

                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])

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

        }

  

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

        printSolution(dist);

    }

  

    // Метод драйвера

    public static void main(String[] args)

    {

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

        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 } };

        ShortestPath t = new ShortestPath();

        t.dijkstra(graph, 0);

    }

}
// Этот код предоставлен Aakash Hasija

питон

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

  
# Библиотека для INT_MAX

import sys

  

class Graph():

  

    def __init__(self, vertices):

        self.V = vertices

        self.graph = [[0 for column in range(vertices)] 

                    for row in range(vertices)]

  

    def printSolution(self, dist):

        print "Vertex \tDistance from Source"

        for node in range(self.V):

            print node, "\t", dist[node]

  

    # Полезная функция для поиска вершины с

    # минимальное значение расстояния от множества вершин

    # еще не включено в дерево кратчайших путей

    def minDistance(self, dist, sptSet):

  

        # Инициализировать минимальное расстояние для следующего узла

        min = sys.maxint

  

        # Поиск не ближайшей вершины не в

        # кратчайший путь

        for v in range(self.V):

            if dist[v] < min and sptSet[v] == False:

                min = dist[v]

                min_index = v

  

        return min_index

  

    # Функция, которая реализует единый источник Дейкстры

    # алгоритм кратчайшего пути для представленного графа

    # использование представления матрицы смежности

    def dijkstra(self, src):

  

        dist = [sys.maxint] * self.V

        dist[src] = 0

        sptSet = [False] * self.V

  

        for cout in range(self.V):

  

            # Выберите минимальное расстояние от вершины до

            # множество вершин, еще не обработанных.

            # u всегда равен src в первой итерации

            u = self.minDistance(dist, sptSet)

  

            # Поместите вершину минимального расстояния в

            # дерево кратчайшего пути

            sptSet[u] = True

  

            # Обновить значение dist соседних вершин

            # выбранной вершины, только если текущий

            # расстояние больше нового расстояния и

            # вершина не в дереве кратчайшего пути

            for v in range(self.V):

                if self.graph[u][v] > 0 and sptSet[v] == False and \

                dist[v] > dist[u] + self.graph[u][v]:

                        dist[v] = dist[u] + self.graph[u][v]

  

        self.printSolution(dist)

  
# Драйверная программа

g = Graph(9)

g.graph = [[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]

        ];

  

g.dijkstra(0);

  
# Этот код предоставлен Divyanshu Mehta

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)

    {

        Console.Write("Vertex \t\t 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);

    }

  

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

    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

Примечания:
1) Код вычисляет кратчайшее расстояние, но не вычисляет информацию о пути. Мы можем создать родительский массив, обновить родительский массив при обновлении расстояния (как реализация prim ) и использовать его, чтобы показать кратчайший путь от источника к различным вершинам.

2) Код предназначен для неориентированного графа, такая же функция дижкстры может быть использована и для ориентированных графов.

3) Код находит кратчайшие расстояния от источника до всех вершин. Если нас интересует только кратчайшее расстояние от источника до единственной цели, мы можем разорвать цикл for, когда выбранная вершина минимального расстояния равна цели (шаг 3.a алгоритма).

4) Сложность времени реализации O (V ^ 2). Если входной граф представлен с использованием списка смежности , его можно уменьшить до O (E log V) с помощью двоичной кучи. Посмотри пожалуйста
Алгоритм Дейкстры для представления списка смежности для более подробной информации.

5) Алгоритм Дейкстры не работает для графов с отрицательными весовыми ребрами. Для графиков с отрицательными весовыми гранями можно использовать алгоритм Беллмана – Форда , который мы вскоре обсудим в отдельном посте.

Алгоритм Дейкстры для представления списка смежности

Печать путей в алгоритме кратчайшего пути Дейкстры

Алгоритм кратчайшего пути Дейкстры с использованием набора в STL

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

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

0.00 (0%) 0 votes