Dijsktrův algoritmus: C++, Python Příklad kódu

Jaká je nejkratší cesta nebo nejkratší vzdálenost?

Cesta ze zdrojového vrcholu do cílového vrcholu, která stojí minimum, je nejkratší cesta nebo nejkratší vzdálenost. V teorii grafů je možné mít více cest od zdroje k cíli. Pokud mezi těmito cestami existuje cesta, která stojí minimální částku, můžeme ji nazvat algoritmem nejkratší cesty.

Zde „Cena“ znamená počet uzlů na trase nebo součet nákladů na každé trase. Cesta může mít jednu nebo více hran. Spojení mezi dvěma vrcholy se nazývá „hrana“. Existují různé typy algoritmů nejkratší cesty, jako je Dijkstrův algoritmus, Bellman-Fordův algoritmus atd.

Zde diskutujeme o Dijkstrově algoritmu

Podívejme se na následující vážený graf:

• Termín „vážený“ znamená přesun nákladů z jednoho uzlu do druhého. Například při přechodu z uzlu 1 do uzlu 2 je cena nebo hmotnost 1.
• Cesta mezi uzlem 1 a uzlem 2 se nazývá hrana.
• „Undirected“ znamená, že můžete přesunout jeden uzel do druhého a zpět na předchozí uzel. Pokud se tedy pokusíme najít všechny cesty z uzlu 1 do uzlu 7, bude to:

Trasa nebo Cesta	Stát
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

Z těchto čtyř tras vidíme, že první cesta nás bude stát 7. Je to tedy cenově nejkratší cesta.

Jak funguje Dijkstrův algoritmus

Dijkstrův algoritmus dokáže najít nejkratší vzdálenost v orientovaných i neorientovaných vážených grafech. Tento algoritmus je chamtivý, protože vždy vybírá nejkratší nebo nejbližší uzel z počátku. Termín „chamtivý“ znamená, že ze souboru výsledků nebo výsledků algoritmus vybere ten nejlepší z nich.

Zde se snažíme najít nejkratší cesty ze všech ostatních tras. Dijkstrův algoritmus tedy najde všechny nejkratší cesty z jednoho cílového uzlu. V důsledku toho se chová jako a chamtivý algoritmus.

V části „příklad“ níže uvidíte postup krok za krokem. Funguje následovně:

Krok 1) Inicializujte počáteční uzel s 0 náklady a zbytek uzlu jako Infinity Cost.
Krok 2) Udržujte pole nebo seznam, abyste mohli sledovat navštívené uzly
Krok 3) Aktualizujte cenu uzlu s minimální cenou. To lze provést porovnáním aktuálních nákladů s náklady na cestu. (Ukázka je uvedena v sekci příkladů)
Krok 4) Pokračujte krokem 3, dokud nenavštívíte všechny uzly.

Po dokončení všech těchto kroků najdeme cestu, která stojí minimum od zdroje k cíli.

Rozdíl mezi Dijkstrou a BFS, DFS

Hlavní rozdíl mezi Dijkstra a BFS-DFS je v tom, že Dijkstra je nejkratší algoritmus hledání cesty a BFS, DFS je algoritmus hledání cesty. V obecných případech BFS a DFS neberou v úvahu náklady při hledání cesty. Tyto algoritmy tedy nemohou zaručit nejkratší cestu.

2D mřížková ukázka toho, jak BFS funguje

Tato ukázka ukazuje, že BFS najde pouze cestu. Nezáleží však na hmotnosti cesty. BFS (První vyhledávání podle šířky) předpokládá, že cestování z jednoho uzlu do druhého bude stát pouze 1.

Ale podívejme se na příklad grafu:

Zde najde cestu v úrovni 2. BFS prochází grafem v pořadí úrovní. Takže to cestuje takto:

Krok 1) Začněte od uzlu „1“ a navštivte všechny sousední uzly 2,3,4

Krok 2) Označte uzel 2,3,4 jako úroveň 1 a navštivte jejich sousední uzly. Bude pokračovat v prozkoumávání všech sousedních uzlů, dokud nedosáhne cílového uzlu.

Pokud jde o DFS, bude procházet cestou od 1 do 7 takto:

• 1→2→3→7 (původní cena 10, cena DFS 3)
• 1→2→6→7 (původní cena 7, cena DFS 3)
• 1→3→7 (původní cena 8, cena DFS 2)
• 1→4→5→7 (původní cena 13, cena DFS 3)

Jak vidíme, DFS počítá náklady na cestu s počtem hloubek nebo počtem hran.

DFS dělá následující:

• DFS může najít cestu ze zdroje (počáteční vrchol) do cíle.
• Nemůže zaručit, zda zjištěná cesta ze zdrojového uzlu do cíle je nejkratší cestou nebo ne.

Nicméně, pokud jde o Dijkstra Algorithm, vybere hrany na základě jejich ceny. Jako chamtivý algoritmus bude vybírat nejlepší cesty nebo cesty s minimálními náklady.

Příklad Dijkstrova algoritmu

Dijkstrův algoritmus používá k výpočtu celkových nákladů na cestu cenu nebo váhu.

Cílem Dijkstrova algoritmu je minimalizovat tyto celkové náklady nebo hmotnost. Ve výše uvedeném příkladu najdeme nejlepší cesty z uzlu 1 do uzlu 7 a poté spočítáme všechny náklady.

V Dijkstrově algoritmu najde nejkratší cesty výpočtem vah. Nebude hledat všechny možné cesty. Ukažme si Dijkstrův algoritmus na příkladu. Například jste byli požádáni, abyste našli nejkratší cestu z uzlu 1 do 7.

Pro tento proces jsou kroky uvedeny níže:

Krok 1) Inicializujte počáteční cenu uzlu na 0.

Zbytek uzlu, přiřaďte „Inf“. To znamená, že mezi počátečním vrcholem (zdrojem) a uzlem neexistuje žádná cesta, nebo cesta ještě není navštívena.

Krok 2) Když vyberete uzel 1, bude označen jako navštívený. Potom aktualizujte všechny sousední sousedy uzlu 1. 2,3,4 jsou sousední uzly uzlu 1.

Při aktualizaci ceny musíme postupovat podle níže uvedeného postupu:

Pomocí výše uvedeného vzorce můžeme aktualizovat náklady každého uzlu. Byli jsme například v uzlu 1 a potřebovali jsme aktualizovat cenu sousedního uzlu 2,3,4.

Po aktualizaci bude cena nebo hmotnost vypadat takto:

Krok 3) Pro uzel „2“, sousedé jsou 6 a 3. Aktualizujeme cenu na „6“ porovnáním nekonečna (aktuální hodnota). Cena uzlu 2 + cena cesty od 2 do 6. Jednoduše řečeno, uzel „6“ bude mít cenu 1+3 nebo 4.

Uzel 3 je sousedem uzlu 2. V předchozím kroku jsme však vypočítali jeho cenu, která byla 7. Nyní, pokud je naše cesta 1-2-3, uzel 3 bude mít cenu 10. Cesta 1-2- 3 bude stát 10, zatímco 1 až 3 bude stát 7.

Krok 4) Pro uzel 3, sousední uzel je 7. Takže porovnáním aktuální hodnoty uzlu 7 s cenou cesty (7+1) nebo 8 aktualizujeme cenu uzlu 7. To je 8.

Najdeme tedy cestu z uzlu 1 do uzlu 7 a je to 1→ 3→ 7. Cena je 8.

Krok 5) Pro uzel 4, odpovídajícím způsobem aktualizujeme náklady na sousední uzel. Takže uzel „5“ bude mít aktualizovanou cenu 8. Po kroku 4,5 to bude vypadat takto:

Nyní má cesta 1-3-7 cenu 8 (dříve). Uzel „7“ nebyl označen jako navštívený, protože z uzlu „7“ můžeme dosáhnout uzel „6“. Cesta „1-2-6“ měla cenu 4. Takže cesta 1-2-6-7 bude mít cenu 7.

Protože 7 < 8, proto bude nejkratší cesta ze zdrojového vrcholu „1“ do cílového vrcholu „7“ 1-2-6-7 a cena je 7. Dříve to bylo 1-3-7 a náklady bylo 8.

Takže konečný graf bude vypadat takto:

Hrana označená černou čarou je naše nejkratší cesta od 1 do 7 a bude nás to stát 7.

Pseudo kód Dijkstrův algoritmus

Zde je pseudokód pro Dijkstrův algoritmus

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++ implementace Dijkstrova algoritmu

Implementovat Dijkstrův algoritmus pomocí C++, zde je kód:

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

Výstup:

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 implementace Dijkstrova algoritmu

Implementovat Dijkstrův algoritmus pomocí krajta, zde je kód:

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)

Výstup:

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

Vidíme, že Algoritmus počítá nejkratší vzdálenost od zdrojového uzlu.

Aplikace Dijkstrova algoritmu

Dijkstra Algo má širokou škálu použití. Mezi nimi je široce používán v oblasti sítí. Zde jsou některé ze skutečného použití Dijkstrova algoritmu:

Dijkstra na mapě Google: V podstatě je tento algoritmus páteří pro hledání nejkratších cest. Jak můžeme vidět z výše uvedeného výstupu fragmentu kódu.

Google nepoužívá jednoduchý Dijkstrův algoritmus. Místo toho používá upravenou verzi. Když vyberete cíl, zobrazí se vám na mapě Google několik cest. Mezi těmito cestami jsou některé cesty seřazeny pro uživatele. Tyto vybrané cesty jsou založeny na „času“. Takže „čas“ je okrajová cena pro nejkratší cestu.

Dijkstra ve směrování IP: IP směrování je síťová terminologie. Znamená to, jak je váš datový paket odesílán do přijímače různými cestami. Tyto cesty se skládají ze směrovačů, serverů atd. V směrování IP existují různé typy protokolů.

Tyto protokoly pomáhají routeru najít nejkratší cesty k odeslání dat. Jeden z názvů protokolů je „OSPF (Open Shortest Path First)“. OSPF používá dijkstra algoritmus. Router udržuje tabulku tras. Každý router sdílí svou tabulku se sousedními routery. Po obdržení aktualizované tabulky musí znovu vypočítat všechny cesty. V té době router používá Dijkstra Algorithm.

Omezení Dijkstrova algoritmu

Dijkstrův algoritmus nemůže zaručit nejkratší cestu v grafu záporné hrany. Dijkstrův algoritmus se řídí těmito metodikami:

• Jedna nejkratší cesta bude vedena z jednoho uzlu do druhého.
• Jakmile je vybrána nejkratší cesta mezi dvěma uzly, nebude znovu počítána.

Zde si všimněte dvou příkladů s negativními okraji.

V levém grafu jsou tři vrcholy. Dijkstra poběží na grafu takto:

Krok 1) Počáteční vrchol „1“ bude inicializován na nulu. Ostatní uzly budou mít nekonečno.

Krok 2) Označte uzel „1“ jako navštívený a zahrňte jej do nejkratší cesty.

Krok 3) Vzdálenost zdrojového uzlu 1 k uzlům „2“ a „3“ je nastavena na nekonečno, protože nejkratší cestu je třeba ještě vypočítat. Takže každá cesta, která bude stát méně než nekonečno, bude přidána k nejkratší cestě (chamtivý přístup).

Krok 4) Aktualizace vzdálenosti od zdrojového vrcholu nebo zdrojového uzlu „1“ na „2“. Aktuální váha bude 5 (5

Krok 5) Nyní, když zkontrolujeme nejkratší vzdálenosti od uzlu „1“, zjistíme, že 5 je nejkratší vzdálenost pro hranu 1–> 2. Takže uzel „2“ bude označen jako navštívený.

Podobně bude uzel „3“ také označen jako navštívený, protože nejkratší vzdálenost je 3.

Pokud však pozorujeme, existuje cesta 1-3-2, která bude stát pouze 2. Ale Dijkstra ukazuje, že z uzlu „1“ do uzlu „2“ je nejkratší vzdálenost 5. Dijkstra tedy nedokázal vypočítat nejkratší vzdálenost správně. Důvod, proč se to stalo, je ten, že Dijkstra je chamtivý algoritmus. Jakmile je tedy uzel označen jako navštívený, nebude znovu zvažován, i když může být k dispozici kratší cesta. K tomuto problému dochází pouze v případě, že okraje mají záporné náklady nebo záporné okraje hmotnosti

Dijkstra v tomto scénáři nedokáže vypočítat nejkratší cestu mezi dvěma uzly. V důsledku toho má tento algoritmus určité nevýhody. K vyřešení tohoto problému negativní hrany se používá jiný algoritmus nazvaný „Bellman-Fordův algoritmus“. Tento algoritmus může pracovat s negativními hranami.

Složitost Dijkstrova algoritmu

Výše uvedená implementace používala dvě smyčky „for“. Tyto smyčky běží pro počet vrcholů. Časová složitost tedy je O(V²). Zde termín „0“ znamená zápis, který dává předpoklad pro Dijkstrův algoritmus.

Graf můžeme uložit pomocí „Prioritní fronty“. Prioritní fronta je binární datová struktura haldy. Bude to efektivnější než 2D matice. Okraj, který bude mít minimální náklady, bude mít vysokou prioritu.

Pak bude časová složitost O(E log(V)). Zde E je počet hran a V je počet vrcholů.

Prostorová složitost je O(V²), protože používáme matici sousednosti (2D pole). Složitost prostoru lze optimalizovat pomocí přilehlého seznamu nebo datové struktury fronty.