Алгоритъмът на Dijsktra: 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, докато бъде посетен целият възел.

След като изпълним всички тези стъпки, ще намерим пътя, който струва минимум от източника до дестинацията.

Разлика между Dijkstra и BFS, DFS

Основната разлика между Dijkstra и BFS-DFS е, че Dijkstra е алгоритъмът за най-кратък път, а BFS, DFS е алгоритъмът за намиране на път. В общи случаи BFS и DFS не вземат предвид цената, докато намират пътя. Така че тези алгоритми не могат да гарантират най-краткия път.

2D решетка демонстрация на това как работи BFS

Демонстрация на 2D мрежа

Algosketch, показващ BFS демонстрация

Тази демонстрация показва, че BFS намира само пътя. Въпреки това не се интересува от теглото на пътя. BFS (Търсене в ширина) предполага, че пътуването от един възел до друг възел ще струва само 1.

Но нека видим примерна графика:

Демонстрация на 2D мрежа

Тук той намира път в ниво 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

Можем да видим, че алгоритъмът изчислява най-късото разстояние от изходния възел.

Приложение на алгоритъма на Дейкстра

Dijkstra Algo има голям набор от приложения. Сред тях той е широко използван в областта на мрежите. Ето част от използването на алгоритъма на Дейкстра в реалния живот:

Dijkstra в картата на Google: По принцип този алгоритъм е гръбнакът за намиране на най-кратките пътища. Както можем да видим от горния изход на кодовия фрагмент.

Приложение на алгоритъма на Дейкстра

Google не използва простия алгоритъм на Дейкстра. Вместо това той използва модифицирана версия. Когато изберете дестинация, тя ви показва множество пътеки в Google Map. Сред тези пътища някои пътища са сортирани за потребителя. Тези избрани пътища се основават на „времето“. И така, „времето“ е предимство за най-краткия път.

Dijkstra в IP маршрутизирането: IP маршрутизиране е мрежова терминология. Това означава как вашият пакет данни се изпраща до получателя по различни пътища. Тези пътища се състоят от рутери, сървъри и т.н. При IP маршрутизирането има различни типове протоколи.

Тези протоколи помагат на рутера да намери най-кратките пътища за изпращане на данните. Едно от имената на протокола е „OSPF (Първо отваряне на най-краткия път)“. OSPF използва алгоритъм dijkstra. Рутерът поддържа таблица с маршрути. Всеки рутер споделя своята таблица със съседни рутери. След като получат актуализираната таблица, те трябва да изчислят отново всички пътища. По това време рутерът използва алгоритъма на Дейкстра.

Ограничение на алгоритъма на Дейкстра

Алгоритъмът на Дейкстра не може да гарантира най-краткия път в графиката с отрицателен край. Алгоритъмът на Дейкстра следва следните методологии:

  • Един най-кратък път ще бъде изведен от един възел до друг.
  • След като бъде избран най-краткият път между два възела, той няма да бъде изчислен отново.

Тук забележете два примера с отрицателни ръбове.

Ограничение на алгоритъма на Дейкстра

В лявата графика, има три върха. Dijkstra ще работи на графиката по следния начин:

Стъпка 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. Така че Дейкстра не успя да изчисли най-краткото дистанция правилно. Причината да се случи е, че Dijkstra е алчен алгоритъм. Така че, след като възел бъде маркиран като посетен, той няма да бъде преразгледан, въпреки че може да има наличен по-кратък път. Този проблем възниква само когато ръбовете имат отрицателни разходи или ръбове с отрицателно тегло

Dijkstra не успява да изчисли най-краткия път между два възела в този сценарий. В резултат на това този алгоритъм има някои недостатъци. За да се реши този проблем с отрицателния край, се използва друг алгоритъм, наречен „алгоритъм на Белман-Форд“. Този алгоритъм може да работи с отрицателни ръбове.

Сложността на алгоритъма на Дейкстра

Реализацията по-горе използва два цикъла „за“. Тези цикли се изпълняват за броя на върховете. И така, времевата сложност е O(V2). Тук терминът "0" означава нотация, която дава предположение за алгоритъма на Дейкстра.

Можем да съхраним графиката с помощта на „Приоритетна опашка“. Приоритетната опашка е двоична структура от данни в стек. Ще бъде по-ефективно от 2D матрица. Край, който ще има минимална цена, ще има висок приоритет.

Тогава времевата сложност ще бъде O(E log(V)). Тук E е броят на ръбовете, а V е броят на върховете.

Космическата сложност е O(V2), тъй като използваме матрица на съседство (2D масив). Сложността на пространството може да бъде оптимизирана с помощта на списък със съседство или структура от данни на опашка.