Dijsktra's algoritme: C++, Python-codevoorbeeld

Wat is de kortste weg of kortste afstand?

Een pad van het bronknooppunt naar het bestemmingsknooppunt dat een minimum kost, is het kortste pad of de kortste afstand. In de grafentheorie is het mogelijk om meerdere routes te hebben van een bron naar een bestemming. Als er tussen deze routes een route is die een minimumbedrag kost, kunnen we dit het kortste pad-algoritme noemen.

Hier betekent “Kosten” het aantal knooppunten in de route of de som van de kosten op elk pad. Een pad kan één of meerdere randen hebben. De verbinding tussen twee hoekpunten wordt "rand" genoemd. Er zijn verschillende soorten kortste-padalgoritmen, zoals het algoritme van Dijkstra, het Bellman-Ford-algoritme, enz.

Hier bespreken we het algoritme van Dijkstra

Laten we eens kijken naar het vervolgwing gewogen grafiek:

Een ongerichte gewogen grafiek
Een ongerichte gewogen grafiek
  • De term ‘gewogen’ betekent het verplaatsen van kosten van het ene knooppunt naar het andere. Als u bijvoorbeeld van knooppunt 1 naar knooppunt 2 gaat, zijn de kosten of het gewicht 1.
  • Het pad tussen knooppunt 1 en knooppunt 2 wordt de rand genoemd.
  • “Ongericht” betekent dat u het ene knooppunt naar het andere kunt verplaatsen en terug naar het vorige knooppunt. Dus als we alle routes van knooppunt 1 tot knooppunt 7 proberen te vinden, wordt het:
Route of pad Kosten
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

Van deze vier routes kunnen we zien dat de eerste route ons 7 gaat kosten. Dit is dus het kortste pad qua kosten.

Kortste weg

Kortste weg

Hoe het algoritme van Dijkstra werkt

Het Dijkstra-algoritme kan de kortste afstand vinden in zowel gerichte als ongerichte gewogen grafieken. Dit algoritme is hebzuchtig omdat het altijd het kortste of dichtstbijzijnde knooppunt vanaf de oorsprong kiest. De term ‘hebzuchtig’ betekent dat het algoritme uit een reeks uitkomsten of resultaten de beste daarvan zal kiezen.

Hier proberen we de kortste paden tussen alle andere routes te vinden. Het algoritme van Dijkstra vindt dus alle kortste paden vanaf één enkel bestemmingsknooppunt. Als gevolg hiervan gedraagt ​​​​het zich als een hebzuchtig algoritme.

In het gedeelte 'Voorbeeld' hieronder ziet u de stapsgewijze aanpak. Het werkt als volgt:

Stap 1) Initialiseer het startknooppunt met 0 kosten en de rest van het knooppunt als Infinity Cost.
Stap 2) Onderhoud een array of lijst om de bezochte knooppunten bij te houden
Stap 3) Werk de knooppuntkosten bij met de minimale kosten. Dit kan worden gedaan door de huidige kosten te vergelijken met de padkosten. (Demonstratie wordt getoond in het voorbeeldgedeelte)
Stap 4) Ga door met stap 3 totdat alle knooppunten zijn bezocht.

Nadat we al deze stappen hebben doorlopen, vinden we het pad dat het minst kost van bron naar bestemming.

Verschil tussen Dijkstra en BFS, DFS

Het belangrijkste verschil tussen Dijkstra en BFS-DFS is dat Dijkstra het kortste padzoekalgoritme is, en BFS, DFS het padzoekalgoritme. In algemene gevallen houden BFS en DFS geen rekening met de kosten bij het vinden van het pad. Deze algoritmen kunnen dus niet het kortste pad garanderen.

2D-rasterdemonstratie van hoe BFS werkt

2D-rasterdemonstratie

Algoschets, schwing BFS-demonstratie

Deze demonstratie geeft aan dat BFS alleen het pad vindt. Het maakt echter niet uit hoe zwaar het pad is. BFS (Breedte-eerste zoekopdracht) gaat ervan uit dat reizen van het ene knooppunt naar het andere knooppunt slechts 1 kost.

Maar laten we een voorbeeldgrafiek bekijken:

2D-rasterdemonstratie

Hier vindt het een pad op niveau 2. BFS doorloopt de grafiek in niveauvolgorde. Het reist dus als:

Stap 1) Begin vanaf knooppunt “1” en bezoek alle aangrenzende knooppunten 2,3,4

Stap 2) Markeer knooppunt 2,3,4 als niveau 1 en bezoek de aangrenzende knooppunten. Het zal doorgaan met het verkennen van alle aangrenzende knooppunten totdat het het bestemmingsknooppunt bereikt.

In termen van DFS zal het het pad van 1 tot 7 doorlopen, zoals hieronderwing:

  • 1 → 2 → 3 → 7 (oorspronkelijke kosten 10, DFS-kosten 3)
  • 1 → 2 → 6 → 7 (oorspronkelijke kosten 7, DFS-kosten 3)
  • 1 → 3 → 7 (oorspronkelijke kosten 8, DFS-kosten 2)
  • 1 → 4 → 5 → 7 (oorspronkelijke kosten 13, DFS-kosten 3)

Zoals we zien, berekent DFS de padkosten met het aantal diepte of het aantal randen.

DFS doet het volgendewing:

  • DFS kan een pad vinden van de bron (beginpunt) naar de bestemming.
  • Het kan niet garanderen of het ontdekte pad van bronknooppunt naar bestemming het kortste pad is of niet.

In termen van het Dijkstra-algoritme zal het echter randen kiezen op basis van hun kosten. Als een hebzuchtig algoritme zal het de beste of de laagste kostenpaden kiezen.

Voorbeeld van het algoritme van Dijkstra

Het algoritme van Dijkstra gebruikt de kosten of het gewicht om de totale kosten van het pad te berekenen.

Voorbeeld van het algoritme van Dijkstra

Het doel van Dijkstra's algoritme is om deze totale kosten of het gewicht te minimaliseren. In het bovenstaande voorbeeld vinden we de beste paden van knooppunt 1 naar knooppunt 7 en berekenen vervolgens alle kosten.

In het algoritme van Dijkstra vindt het de kortste paden door gewichten te berekenen. Er wordt niet naar alle mogelijke paden gezocht. Laten we het algoritme van Dijkstra demonstreren met een voorbeeld. Er is u bijvoorbeeld gevraagd het kortste pad van knooppunt 1 naar 7 te vinden.

Voor dit proces worden hieronder de stappen gegeven:

Stap 1) Initialiseer de kosten van het startknooppunt naar 0.

Rest van het knooppunt, toewijzen “Inf”. Het betekent dat er geen pad bestaat tussen het startpunt (de bron) en het knooppunt, of dat het pad nog niet is bezocht.

Voorbeeld van het algoritme van Dijkstra

Stap 2) Wanneer u knooppunt 1 selecteert, wordt dit gemarkeerd als bezocht. Werk vervolgens alle aangrenzende knooppunten van knooppunt 1 bij. 2,3,4 zijn de aangrenzende knooppunten van knooppunt 1.

Bij het bijwerken van kosten moeten we de onderstaande procedure volgen:

Voorbeeld van het algoritme van Dijkstra

We kunnen de kosten van elk knooppunt bijwerken met behulp van de bovenstaande formule. We bevonden ons bijvoorbeeld op knooppunt 1 en we moesten de kosten van het aangrenzende knooppunt 2,3,4 bijwerken.

Na het bijwerken zien de kosten of het gewicht er als volgt uit:

Voorbeeld van het algoritme van Dijkstra

Stap 3) Voor knooppunt “2”, buren zijn 6 en 3. We werken de kosten bij op "6" door oneindig (huidige waarde) te vergelijken. De kosten van knooppunt 2 + pad kosten van 2 naar 6. Simpel gezegd: knooppunt “6” heeft de kosten van 1+3 of 4.

Voorbeeld van het algoritme van Dijkstra

Knooppunt 3 is een buur van knooppunt 2. We hebben echter de kosten ervan in de vorige stap berekend, namelijk 7. Als ons pad nu 1-2-3 is, heeft knooppunt 3 een kostprijs van 10. Pad 1-2- 3 kost 10, terwijl 1 tot 3 7 kost.

Stap 4) Voor knooppunt 3, het aangrenzende knooppunt is 7. Dus als we de huidige waarde van knooppunt 7 vergelijken met de padkosten (7+1) of 8, zullen we de kosten van knooppunt 7 bijwerken. Dat is 8.

We vinden dus een pad van knooppunt 1 naar knooppunt 7, en het is 1 → 3 → 7. De kosten zijn 8.

Stap 5) Voor knooppunt 4, we zullen de kosten van het aangrenzende knooppunt dienovereenkomstig bijwerken. Knooppunt “5” heeft dus een bijgewerkte kostprijs van 8. Na stap 4,5 en XNUMX ziet het er als volgt uit:

Voorbeeld van het algoritme van Dijkstra

Nu heeft het pad 1-3-7 de kosten van 8 (voorheen). Knooppunt “7” is niet gemarkeerd als bezocht, omdat we knooppunt “7” kunnen bereiken vanaf knooppunt “6”. Het pad “1-2-6” kostte 4. Dus het pad 1-2-6-7 kost 7.

Aangezien 7 < 8, is het kortste pad van bronpunt “1” naar bestemmingspunt “7” daarom 1-2-6-7, en de kosten zijn 7. Voorheen was dit 1-3-7, en de kosten was 8.

De uiteindelijke grafiek ziet er dus als volgt uit:

Voorbeeld van het algoritme van Dijkstra

De rand gemarkeerd met een zwarte lijn is ons kortste pad van 1 naar 7, en het kost ons 7.

Pseudocode Dijkstra's algoritme

Hier is de pseudo-code voor Dijkstra's algoritme

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++ implementatie Dijkstra's algoritme

Om het algoritme van Dijkstra te implementeren met behulp van C + +, hier is de code:

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

Output:

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-implementatie Dijkstra's algoritme

Om het algoritme van Dijkstra te implementeren met behulp van python, hier is de code:

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)

Output:

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

We kunnen zien dat het algoritme de kortste afstand vanaf het bronknooppunt berekent.

Toepassing van het Dijkstra-algoritme

De Dijkstra Algo heeft een groot aantal toepassingen. Onder deze wordt het veel gebruikt op het gebied van netwerken. Hier zijn enkele voorbeelden van het gebruik van Dijkstra's algoritme in de praktijk:

Dijkstra op Google map: Kortom, dit algoritme vormt de ruggengraat voor het vinden van de kortste paden. Zoals we kunnen zien aan de hand van de bovenstaande codefragmentuitvoer.

Toepassing van het Dijkstra-algoritme

Google gebruikt niet het eenvoudige Dijkstra-algoritme. In plaats daarvan wordt een aangepaste versie gebruikt. Wanneer u een bestemming selecteert, worden er meerdere paden in Google Maps weergegeven. Onder deze paden zijn enkele paden voor de gebruiker uitgezocht. Deze geselecteerde paden zijn gebaseerd op de “tijd”. “Tijd” is dus een randkost voor het kortste pad.

Dijkstra in IP-routing: IP-routering is een netwerkterminologie. Het betekent hoe uw datapakket via verschillende paden naar de ontvanger wordt verzonden. Deze paden bestaan ​​uit routers, servers, enz. Bij IP-routering zijn er verschillende soorten protocollen.

Deze protocollen helpen de router de kortste paden te vinden om de gegevens te verzenden. Eén van de protocolnamen is “OSPF (Open Shortest Path First)”. OSPF gebruikt het dijkstra-algoritme. De router houdt een tabel met routes bij. Elke router shares de tabel met naburige routers. Nadat ze de bijgewerkte tabel hebben ontvangen, moeten ze alle paden opnieuw berekenen. Op dat moment maakt de router gebruik van het Dijkstra-algoritme.

Beperking van Dijkstra's algoritme

Het Dijkstra-algoritme kan het kortste pad in de negatieve randgrafiek niet garanderen. Het Dijkstra-algoritme volgt deze methodologieën:

  • Er wordt één kortste pad genomen van het ene knooppunt naar het andere.
  • Zodra het kortste pad tussen twee knooppunten is geselecteerd, wordt dit niet opnieuw berekend.

Let hier op twee voorbeelden met negatieve randen.

Beperking van Dijkstra's algoritme

In de linkergrafiek, er zijn drie hoekpunten. Dijkstra zal op de Graph draaien zoals de volgendewing:

Stap 1) Startpunt “1” wordt op nul geïnitialiseerd. De andere knooppunten hebben oneindigheid.

Beperking van Dijkstra's algoritme

Stap 2) Markeer knooppunt “1” als bezocht en neem het op in het kortste pad.

Stap 3) De afstand van bronknooppunt 1 tot knooppunten “2” en “3” is ingesteld op oneindig, omdat het kortste pad nog moet worden berekend. Elk pad dat minder dan oneindig kost, wordt dus toegevoegd aan het kortste pad (hebzuchtige benadering).

Stap 4) De afstand van bronvertex of bronknooppunt “1” bijwerken naar “2”. Het huidige gewicht is 5 (5

Beperking van Dijkstra's algoritme

Stap 5) Als we nu de kortste afstanden vanaf knooppunt “1” controleren, zien we dat 5 de kortste afstand is voor rand 1–> 2. Knooppunt “2” wordt dus gemarkeerd als bezocht.

Op dezelfde manier wordt knooppunt “3” ook gemarkeerd als bezocht, aangezien de kortste afstand 3 is.

Als we echter observeren, is er een pad 1-3-2 dat slechts 2 kost. Maar de Dijkstra laat zien dat van knooppunt “1” naar knooppunt “2” de kortste afstand 5 is. Dijkstra slaagde er dus niet in de kortste afstand te berekenen. afstand correct. De reden dat dit gebeurde is dat Dijkstra een hebzuchtig algoritme is. Zodra een knooppunt als bezocht is gemarkeerd, wordt dit dus niet meer heroverwogen, hoewel er mogelijk een korter pad beschikbaar is. Dit probleem treedt alleen op als de randen negatieve kosten of negatieve gewichtsranden hebben

Dijkstra slaagt er in dit scenario niet in om het kortste pad tussen twee knooppunten te berekenen. Als gevolg hiervan heeft dit algoritme enkele nadelen. Om dit negatieve randprobleem op te lossen, wordt een ander algoritme gebruikt, genaamd “Bellman-Ford Algorithm”. Dat algoritme kan werken met negatieve randen.

Dijkstra's algoritme Complexity

De bovenstaande implementatie gebruikte twee “for”-lussen. Deze lussen lopen voor het aantal hoekpunten. Dus de tijd complexhet is O(V2). Hier betekent de term “0” een notatie die een aanname geeft voor het Dijkstra-algoritme.

We kunnen de grafiek opslaan met behulp van de "Prioriteitswachtrij". Een prioriteitswachtrij is een binaire heap-gegevensstructuur. Het zal efficiënter zijn dan een 2D-matrix. Een voorsprong met minimale kosten zal een hoge prioriteit hebben.

Dan is de tijd complexzal zijn O (E log (V)). Hier is E het aantal randen en V het aantal hoekpunten.

De ruimte complexhet is O(V2), omdat we een aangrenzende matrix gebruiken (2D-reeks). Ruimte complexDe activiteit kan worden geoptimaliseerd met behulp van een aangrenzende lijst of een wachtrijgegevensstructuur.