Алгоритм Дейсктри: C++, Python Приклад коду

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

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

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

Тут ми обговорюємо алгоритм Дейкстри

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

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

Маршрут або шлях	Коштувати
1-2-6-7	(1+3+3) = 7
1-2-3-7	(1+9+1) = 11
1-3-7	(7+1) = 8
1-4-5-7	(6+2+5) = 13

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

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

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

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

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

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

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

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

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

2D сітка демонструє, як працює BFS

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

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

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

Тут він знаходить шлях на рівні 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.

Решта вузла, призначити «Inf». Це означає, що не існує шляху між початковою вершиною (джерелом) і вузлом, або шлях ще не відвіданий.

Крок 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.

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

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

Dijkstra(G, S):  
  for each vertex V in G
    distance[V] & lt; - Infinity
    previous[V] & lt; - NULL
  if V does not equal S, then, 
    (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
   U & lt; - Extract the MIN from Q
   For each unvisited adjacent V of U
   TotalDistance & lt; - distance[U] + edge_cost(U, V)
   if TotalDistance is less than distance[V], then
     distance[V] & lt; - TotalDistance
     previous[V] & lt; - 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] & amp; & 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] & amp; & graph[U][j] & amp; &
          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 реалізація алгоритму Дейкстри

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

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] & lt; = _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 & lt;
    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 (спершу відкрити найкоротший шлях)». OSPF використовує алгоритм Дейкстри. Маршрутизатор підтримує таблицю маршрутів. Кожен маршрутизатор ділиться своєю таблицею з сусідніми маршрутизаторами. Після отримання оновленої таблиці вони повинні знову обчислити всі шляхи. У цей час маршрутизатор використовує алгоритм Дейкстри.

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

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

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

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

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

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

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

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

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

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

Так само вузол «3» також буде позначено як відвіданий, оскільки найкоротша відстань дорівнює 3.

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

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

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

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

Ми можемо зберегти графік за допомогою «черги пріоритетів». Пріоритетна черга — це двійкова структура даних купи. Це буде ефективніше, ніж 2D матриця. Край, який матиме мінімальну вартість, матиме високий пріоритет.

Тоді складність у часі буде O(E log(V)). Тут E — кількість ребер, а V — кількість вершин.

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