Алгоритм Дейкстри в Python & C++ (Приклад)

Який найкоротший шлях або найкоротша відстань?

Шлях від вершини джерела до вершини призначення, який має мінімальну вартість, називається найкоротшим шляхом або найкоротшою відстанню. У теорії графів можливо мати кілька маршрутів від джерела до пункту призначення. Серед цих маршрутів, якщо є маршрут з мінімальною вартістю, ми називаємо його найкоротшим шляхом.

Тут «вартість» означає кількість вузлів у маршруті або суму витрат на кожному ребрі. Шлях може мати одне або кілька ребер. З'єднання між двома вершинами називається «ребром». Існують різні типи алгоритмів пошуку найкоротшого шляху, такі як алгоритм Дейкстри та алгоритм Беллмана-Форда.

Тут ми обговорюємо алгоритм Дейкстри. Розглянемо наступний зважений графік:

Неорієнтований-зважений граф

• Термін «зважений» означає вартість переміщення від одного вузла до іншого. Наприклад, для переміщення від вузла 1 до вузла 2 вартість або вага дорівнює 1.
• Шлях між вузлом 1 та вузлом 2 називається ребром.
• «Неорієнтований» означає, що ви можете переходити від одного вузла до іншого та назад до попереднього вузла. Отже, якщо ми спробуємо знайти всі маршрути від вузла 1 до вузла 7, вони будуть:

Серед цих чотирьох маршрутів ми бачимо, що перший маршрут коштує 7. Отже, це найкоротший шлях з точки зору вартості.

Найкоротший шлях

Як працює алгоритм Дейкстри

Алгоритм Дейкстри може знаходити найкоротшу відстань як у орієнтованих, так і в неорієнтованих зважених графах. Цей алгоритм є жадібним, оскільки він завжди вибирає найкоротший або найближчий вузол від початку координат. Термін «жадібний» означає, що серед набору результатів або підтверджень алгоритм вибере найкращий з них.

Тут ми намагаємося знайти найкоротші шляхи серед усіх інших маршрутів. Отже, алгоритм Дейкстри знаходить усі найкоротші шляхи від одного вихідного вузла. В результаті він поводиться як жадібний алгоритм.

У розділі «приклад» нижче ви побачите покроковий підхід. Він працює наступним чином:

Крок 1) Ініціалізуйте початковий вузол з 0 вартістю, а решту вузлів з нескінченною вартістю.
Крок 2) Зберігати масив або список для зберігання track відвіданих вузлів.
Крок 3) Оновіть вартість вузла, встановивши мінімальну вартість. Це можна зробити, порівнявши поточну вартість з вартістю шляху (продемонстровано в розділі прикладів).
Крок 4) Продовжуйте крок 3, доки не будуть відвідані всі вузли.

Після виконання всіх цих кроків ми знайдемо мінімальний шлях від джерела до пункту призначення.

Різниця між Дейкстрою та BFS, DFS

Основна відмінність між алгоритмом Дейкстри та BFS-DFS полягає в тому, що Дейкстра є алгоритмом пошуку найкоротшого шляху, тоді як BFS та DFS є загальними алгоритмами пошуку шляху. У загальних випадках BFS та DFS не враховують вартість ребра під час пошуку шляху. Отже, ці алгоритми не можуть гарантувати найкоротший шлях.

Демонстрація двовимірної сітки принципу роботи BFS

Алгоскетч, показуючи демонстрацію BFS

Ця демонстрація показує, що BFS знаходить лише шлях. Однак він не зважає на вагу шляху. BFS (Пошук вшир) передбачає, що подорож від одного вузла до іншого коштуватиме лише 1.

Давайте розглянемо приклад графіка:

Тут BFS знаходить шлях на рівні 2. BFS проходить граф у порядку рівнів. Отже, він рухається так:

Крок 1) Почніть з вузла «1» та відвідайте всі сусідні вузли 2, 3, 4.

Крок 2) Позначте вузли 2, 3, 4 як рівень 1 та відвідайте сусідні вузли. Він продовжить дослідження всіх сусідніх вузлів, доки не досягне вузла призначення.

З точки зору DFS, він пройде шлях від 1 до 7, як показано нижче:

• 1→2→3→7 (Первинна вартість 10, вартість DFS 3)
• 1→2→6→7 (Первинна вартість 7, вартість DFS 3)
• 1→3→7 (Первинна вартість 8, DFS вартість 2)
• 1→4→5→7 (Первинна вартість 13, вартість DFS 3)

Як бачимо, DFS обчислює вартість свого шляху за кількістю ребер. DFS робить наступне:

• DFS може знайти шлях від джерела (початкової вершини) до пункту призначення.
• Він не може гарантувати, чи знайдений шлях від вихідного вузла до пункту призначення є найкоротшим шляхом чи ні.

Однак, з точки зору алгоритму Дейкстри, він вибирає ребра на основі їхньої вартості. Як жадібний алгоритм, він вибиратиме шляхи з мінімальною вартістю.

Приклад алгоритму Дейкстри

Алгоритм Дейкстри використовує вартість або вагу для обчислення загальної вартості шляху.

Метою алгоритму Дейкстри є мінімізація загальної вартості або ваги. У наведеному вище прикладі ми знаходимо найкращі шляхи від вузла 1 до вузла 7, а потім обчислюємо всі витрати.

В алгоритмі Дейкстри найкоротші шляхи будуть знайдені шляхом обчислення вагових коефіцієнтів. Він не буде шукати всі можливі шляхи. Давайте продемонструємо алгоритм Дейкстри на прикладі. Наприклад, вас попросили знайти найкоротший шлях від вузла 1 до 7.

Нижче наведено кроки для цього процесу.

Крок 1) Ініціалізуйте вартість початкового вузла рівною 0. Призначте «Інформація» до решти вузлів. Це означає, що шляху між джерелом і вузлом не існує, або шлях ще не відвідано.

Крок 2) Коли ви виберете вузол 1, він буде позначений як відвіданий. Потім оновіть усі сусідні вузли вузла 1. 2, 3, 4 – це сусідні вузли вузла 1.

Оновлюючи вартість, ми повинні дотримуватися наведеної нижче процедури.

Ми можемо оновити вартість кожного вузла за допомогою наведеної вище формули. Наприклад, ми були на вузлі 1, і нам потрібно було оновити вартість сусідніх вузлів 2, 3, 4. Після оновлення витрати виглядатимуть так:

Крок 3) Для вузла «2» сусідами є 6 та 3. Ми оновлюємо вартість на «6», порівнюючи нескінченність (поточне значення) з вартістю вузла 2 + вартість шляху від 2 до 6. Простіше кажучи, вузол «6» матиме вартість 1+3 або 4.

Вузол 3 є сусідом вузла 2. Однак ми обчислили його вартість на попередньому кроці, яка була 7. Тепер, якщо наш шлях 1-2-3, вузол 3 матиме вартість 10. Шлях 1-2- 3 коштуватимуть 10, а від 1 до 3 – 7.

Крок 4) Для вузла 3 сусідній вузол має номер 7. Отже, порівнюючи поточне значення вузла 7 з вартістю шляху (7+1) або 8, ми оновимо вартість вузла 7. Це 8. Отже, ми знаходимо шлях від вузла 1 до вузла 7, і це 1→3→7. Вартість дорівнює 8.

Крок 5) Для вузла 4 ми відповідно оновимо вартість сусіднього вузла. Отже, вузол «5» матиме оновлену вартість 8. Після кроків 4 та 5 це виглядатиме так:

Тепер шлях 1-3-7 має вартість 8 (раніше). Вузол «7» не був позначений як відвіданий, оскільки ми можемо дістатися до вузла «7» з вузла «6». Шлях «1-2-6» мав вартість 4. Отже, шлях 1-2-6-7 матиме вартість 7.

Оскільки 7 < 8, найкоротший шлях від вихідної вершини «1» до кінцевої вершини «7» буде 1-2-6-7, а вартість дорівнюватиме 7. Раніше було 1-3-7, а вартість дорівнювала 8. Отже, остаточний графік виглядатиме так:

Край, позначений чорною лінією, є нашим найкоротшим шляхом від 1 до 7, і він коштуватиме нам 7.

Псевдо Code Алгоритм Дейкстри

Ось псевдокод алгоритму Дейкстри:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Реалізація алгоритму Дейкстри

Для реалізації алгоритму Дейкстри використовують C++, ось код:

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] && distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] && graph[U][j] &&
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

вихід:

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

Python Реалізація алгоритму Дейкстри

Для реалізації алгоритму Дейкстри використовують Python, ось код:

num_of_vertex = 7
def minimumDistance(distance, visited):
    _min = 1e11
    min_index = 1e11
    for i in range(num_of_vertex):
        if not visited[i] and distance[i] <= _min:
            _min = distance[i]
            min_index = i
    return min_index

def printParentNode(parent, i):
    if parent[i] == -1:
        return
    printParentNode(parent, parent[i])
    print("{} ".format(i + 1), end="")

def dijkstra(graph, src):
    distance = list()
    visited = list()
    parent = list()
    for i in range(num_of_vertex):
        parent.append(-1)
        distance.append(1e11)
        visited.append(False)
    distance[src] = 0
    for i in range(num_of_vertex - 1):
        U = minimumDistance(distance, visited)
        visited[U] = True
        for j in range(num_of_vertex):
            curr_distance = distance[U] + graph[U][j]
            if not visited[j] and graph[U][j] and curr_distance < distance[j]:
                parent[j] = U
                distance[j] = curr_distance
    print("Vertex\t\tDistance\tPath")
    for i in range(num_of_vertex):
        print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end="")
        printParentNode(parent, i)
        print("")

graph = [
    [0, 1, 7, 6, 0, 0, 0],
    [1, 0, 9, 0, 0, 3, 0],
    [7, 9, 0, 0, 0, 0, 1],
    [6, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 3],
    [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

вихід:

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

Ми бачимо, що алгоритм обчислює найкоротшу відстань від вихідного вузла.

Застосування алгоритму Дейкстри

Алгоритм Дейкстри має широкий спектр застосувань. Серед них він широко використовується в галузі мереж. Ось деякі реальні випадки використання алгоритму Дейкстри:

Дейкстра в Google карти: Цей алгоритм є основою для пошуку найкоротших шляхів, як ми можемо бачити з наведеного вище фрагмента коду.

Google не використовує простий алгоритм Дейкстри. Натомість він використовує модифіковану версію. Коли ви вибираєте пункт призначення, він показує вам кілька шляхів у Google Карти. Серед цих шляхів деякі відсортовані для користувача. Ці шляхи вибираються на основі «часу». Отже, «час» – це вартість ребра для найкоротшого шляху.

Дейкстра в IP-маршрутизації: IP-маршрутизація – це мережева термінологія. Вона описує, як ваш пакет даних надсилається одержувачу різними шляхами. Ці шляхи складаються з маршрутизаторів, серверів та іншого обладнання. В IP-маршрутизації існують різні типи протоколів.

Ці протоколи допомагають маршрутизатору знаходити найкоротші шляхи для надсилання даних. Одна з назв протоколів - «OSPF (Open Shortest Path First - Відкрити найкоротший шлях першим)». OSPF використовує алгоритм Дейкстри. Маршрутизатор підтримує таблицю маршрутів. Кожен маршрутизатор надає доступ до своєї таблиці сусіднім маршрутизаторам. Після отримання оновленої таблиці вони повинні знову обчислити всі шляхи. У цьому випадку маршрутизатор використовує алгоритм Дейкстри.

Обмеження алгоритму Дейкстри

Алгоритм Дейкстри не може гарантувати найкоротший шлях у графі з негативними ребрами. Алгоритм Дейкстри дотримується таких принципів:

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

Зверніть увагу на два приклади з негативними краями.

На лівому графіку, є три вершини. Дейкстра працюватиме на графі наступним чином:

Крок 1) Початкова вершина «1» буде ініціалізована нулем. Інші вузли матимуть нескінченність.

Крок 2) Позначте вузол «1» як відвіданий та включіть його до найкоротшого шляху.

Крок 3) Відстань від вихідного вузла 1 до вузлів «2» та «3» встановлюється на нескінченність, оскільки найкоротший шлях ще не обчислено. Отже, будь-який шлях, вартість якого менша за нескінченність, буде додано до найкоротшого шляху (жадібний підхід).

Крок 4) Оновлення відстані від вихідної вершини «1» до «2». Поточна вага становитиме 5 (5 < нескінченність). Аналогічно, оновіть відстань від вузла «1» до «3» з вагою 3.

Крок 5) Тепер, якщо ми перевіримо найкоротші відстані від вузла «1», ми виявимо, що 5 – це найкоротша відстань для ребра 1→2. Отже, вузол «2» буде позначено як відвіданий. Аналогічно, вузол «3» також буде позначено як відвіданий, оскільки найкоротша відстань дорівнює 3.

Однак, якщо ми спостерігаємо, існує шлях 1-3-2, який коштуватиме лише 2. Але Дейкстра показує, що від вузла «1» до вузла «2» найкоротша відстань дорівнює 5. Отже, Дейкстра не зміг правильно розрахувати найкоротшу відстань. Причина полягає в тому, що Дейкстра — це жадібний алгоритм. Тож, як тільки вузол позначено як відвіданий, його не буде розглянуто повторно, хоча може бути доступний коротший шлях. Ця проблема виникає лише тоді, коли ребра мають негативні витрати або негативну вагу ребер.

Дейкстра не може обчислити найкоротший шлях між двома вузлами в цьому сценарії. Як наслідок, цей алгоритм має деякі недоліки. Для вирішення цієї проблеми негативних ребер використовується інший алгоритм, який називається «алгоритм Беллмана-Форда». Цей алгоритм може працювати з негативними ребрами.

Складність алгоритму Дейкстри

Наведена вище реалізація використовувала два цикли «for». Ці цикли виконуються для кількості вершин. Отже, часова складність є O(V²)Тут термін «O» – це позначення, яке дає припущення для алгоритму Дейкстри.

Ми можемо зберігати граф, використовуючи «чергу пріоритетів». Черга пріоритетів — це двійкова структура даних купи. Вона буде ефективнішою, ніж двовимірна матриця. Ребро з мінімальною вартістю матиме високий пріоритет. Тоді часова складність буде O(E log V). Тут E — кількість ребер, а V — кількість вершин.

Космічна складність є O(V²), оскільки ми використовуємо матрицю суміжності (2D масив). Складність простору можна оптимізувати за допомогою списку суміжності або структури даних черги.

Поширені запитання