Dijsktras Algorithmus: C++, Python-Codebeispiel

Was ist der kürzeste Weg oder die kürzeste Entfernung?

Ein Pfad vom Quellscheitelpunkt zum Zielscheitelpunkt, der minimal kostet, ist der kürzeste Weg oder die kürzeste Entfernung. In der Graphentheorie ist es möglich, mehrere Routen von einer Quelle zu einem Ziel zu haben. Wenn zwischen diesen Routen eine Route mit minimalen Kosten vorhanden ist, können wir sie als Algorithmus für den kürzesten Weg bezeichnen.

Hier bedeutet „Kosten“ die Anzahl der Knoten in der Route oder die Summe der Kosten auf jedem Pfad. Ein Pfad kann eine oder mehrere Kanten haben. Die Verbindung zwischen zwei Eckpunkten wird „Kante“ genannt. Es gibt verschiedene Arten von Algorithmen für kürzeste Wege, wie den Dijkstra-Algorithmus, den Bellman-Ford-Algorithmus usw.

Hier diskutieren wir über den Dijkstra-Algorithmus

Schauen wir uns das Folgende anwing gewichtete Grafik:

Ein ungerichtet-gewichteter Graph
Ein ungerichtet-gewichteter Graph
  • Der Begriff „gewichtet“ bedeutet, dass Kosten von einem Knoten auf einen anderen verschoben werden. Wenn Sie beispielsweise von Knoten 1 zu Knoten 2 wechseln, betragen die Kosten oder das Gewicht 1.
  • Der Pfad zwischen Knoten 1 und Knoten 2 wird als Kante bezeichnet.
  • „Ungerichtet“ bedeutet, dass Sie einen Knoten zu einem anderen und zurück zum vorherigen Knoten verschieben können. Wenn wir also versuchen, alle Routen von Knoten 1 bis Knoten 7 zu finden, dann sieht es so aus:
Route oder Pfad 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

Unter diesen vier Routen können wir sehen, dass die erste Route uns 7 kosten wird. Sie ist also kostenmäßig der kürzeste Weg.

Kürzester Weg

Kürzester Weg

Wie Dijkstras Algorithmus funktioniert

Der Dijkstra-Algorithmus kann die kürzeste Entfernung sowohl in gerichteten als auch in ungerichteten gewichteten Diagrammen finden. Dieser Algorithmus ist gierig, da er immer den kürzesten oder nächstgelegenen Knoten vom Ursprung aus wählt. Der Begriff „gierig“ bedeutet, dass der Algorithmus aus einer Reihe von Ergebnissen oder Resultaten die besten davon auswählt.

Hier versuchen wir, unter allen anderen Routen die kürzesten Wege zu finden. Der Dijkstra-Algorithmus findet also alle kürzesten Pfade von einem einzelnen Zielknoten. Infolgedessen verhält es sich wie ein Gieriger Algorithmus.

Im Abschnitt „Beispiel“ unten sehen Sie die schrittweise Vorgehensweise. Es funktioniert wie folgt:

Schritt 1) Initialisieren Sie den Startknoten mit 0 Kosten und den Rest des Knotens mit Unendlichkeitskosten.
Schritt 2) Pflegen Sie ein Array oder eine Liste, um den Überblick über die besuchten Knoten zu behalten
Schritt 3) Aktualisieren Sie die Knotenkosten mit den Mindestkosten. Dies kann durch einen Vergleich der aktuellen Kosten mit den Pfadkosten erfolgen. (Demonstration wird im Beispielabschnitt gezeigt)
Schritt 4) Fahren Sie mit Schritt 3 fort, bis der gesamte Knoten besucht ist.

Nachdem wir alle diese Schritte ausgeführt haben, finden wir den Weg, der von der Quelle zum Ziel am wenigsten kostet.

Unterschied zwischen Dijkstra und BFS, DFS

Der Hauptunterschied zwischen Dijkstra und BFS-DFS besteht darin, dass Dijkstra der kürzeste Pfadfindungsalgorithmus ist und BFS, DFS der Pfadfindungsalgorithmus ist. Im Allgemeinen berücksichtigen BFS und DFS die Kosten bei der Pfadfindung nicht. Daher können diese Algorithmen nicht den kürzesten Weg garantieren.

2D-Gitterdemonstration der Funktionsweise von BFS

2D-Gitterdemonstration

Algoskizze, showing BFS-Demonstration

Diese Demonstration zeigt, dass BFS nur den Pfad findet. Das Gewicht des Pfades ist ihm jedoch egal. BFS (Breitensuche) geht davon aus, dass die Fahrt von einem Knoten zu einem anderen Knoten nur 1 kostet.

Aber sehen wir uns eine Beispielgrafik an:

2D-Gitterdemonstration

Hier findet es einen Pfad in Ebene 2. BFS durchläuft den Graphen in der Reihenfolge der Ebenen. Es reist also wie folgt:

Schritt 1) Beginnen Sie mit Knoten „1“ und besuchen Sie alle angrenzenden Knoten 2,3,4

Schritt 2) Markieren Sie Knoten 2,3,4 als Ebene 1 und besuchen Sie die angrenzenden Knoten. Es wird weiterhin alle benachbarten Knoten erkunden, bis es den Zielknoten erreicht.

In Bezug auf DFS wird der Pfad von 1 bis 7 wie folgt durchlaufenwing:

  • 1→2→3→7 (Ursprüngliche Kosten 10, DFS-Kosten 3)
  • 1→2→6→7 (Ursprüngliche Kosten 7, DFS-Kosten 3)
  • 1→3→7 (Ursprüngliche Kosten 8, DFS-Kosten 2)
  • 1→4→5→7 (Ursprüngliche Kosten 13, DFS-Kosten 3)

Wie wir sehen, berechnet DFS seine Pfadkosten anhand der Anzahl der Tiefen oder Kanten.

DFS führt Folgendes auswing:

  • DFS kann einen Pfad von der Quelle (Startscheitelpunkt) zum Ziel finden.
  • Es kann nicht garantiert werden, ob der vom Quellknoten zum Ziel ermittelte Pfad der kürzeste ist oder nicht.

Im Sinne des Dijkstra-Algorithmus werden Kanten jedoch auf der Grundlage ihrer Kosten ausgewählt. Als gieriger Algorithmus wählt er die besten oder minimalsten Kostenpfade aus.

Beispiel für Dijkstras Algorithmus

Der Dijkstra-Algorithmus verwendet die Kosten oder das Gewicht, um die Gesamtkosten des Pfades zu berechnen.

Beispiel für Dijkstras Algorithmus

Das Ziel des Dijkstra-Algorithmus besteht darin, diese Gesamtkosten bzw. dieses Gesamtgewicht zu minimieren. Im oben gezeigten Beispiel finden wir die besten Pfade von Knoten 1 zu Knoten 7 und berechnen dann alle Kosten.

Im Dijkstra-Algorithmus werden die kürzesten Wege durch Berechnung von Gewichten ermittelt. Es wird nicht nach allen möglichen Pfaden gesucht. Lassen Sie uns den Dijkstra-Algorithmus anhand eines Beispiels demonstrieren. Sie wurden beispielsweise gebeten, den kürzesten Weg von Knoten 1 nach 7 zu finden.

Für diesen Prozess sind die folgenden Schritte aufgeführt:

Schritt 1) Initialisieren Sie die Startknotenkosten auf 0.

Rest des Knotens, zuweisen „Inf“. Dies bedeutet, dass zwischen dem Startscheitelpunkt (der Quelle) und dem Knoten kein Pfad vorhanden ist oder der Pfad noch nicht besucht wurde.

Beispiel für Dijkstras Algorithmus

Schritt 2) Wenn Sie Knoten 1 auswählen, wird dieser als besucht markiert. Aktualisieren Sie dann alle benachbarten Nachbarn von Knoten 1. 2,3,4 sind die Nachbarknoten von Knoten 1.

Beim Aktualisieren von Kosten müssen wir das folgende Verfahren befolgen:

Beispiel für Dijkstras Algorithmus

Wir können die Kosten jedes Knotens mithilfe der obigen Formel aktualisieren. Wir befanden uns beispielsweise am Knoten 1 und mussten die Kosten des benachbarten Knotens 2,3,4 aktualisieren.

Nach der Aktualisierung sehen die Kosten bzw. das Gewicht wie folgt aus:

Beispiel für Dijkstras Algorithmus

Schritt 3) Für Knoten „2“ Nachbarn sind 6 und 3. Wir aktualisieren die Kosten auf „6“, indem wir Unendlich (aktueller Wert) vergleichen. Die Kosten für Knoten 2 + Pfadkosten liegen zwischen 2 und 6. Einfach ausgedrückt hat Knoten „6“ die Kosten von 1+3 oder 4.

Beispiel für Dijkstras Algorithmus

Knoten 3 ist ein Nachbar von Knoten 2. Wir haben jedoch im vorherigen Schritt seine Kosten berechnet, die 7 betrugen. Wenn unser Pfad nun 1-2-3 ist, hat Knoten 3 Kosten von 10. Pfad 1-2- 3 kosten 10, während 1 bis 3 7 kosten.

Schritt 4) Für Knoten 3: Der Nachbarknoten ist 7. Wenn wir also den aktuellen Wert von Knoten 7 mit den Pfadkosten (7+1) oder 8 vergleichen, aktualisieren wir die Kosten von Knoten 7. Das ist 8.

Wir finden also einen Pfad von Knoten 1 zu Knoten 7, und dieser ist 1→ 3→ 7. Die Kosten betragen 8.

Schritt 5) Für Knoten 4: Wir werden die Kosten für den angrenzenden Knoten entsprechend aktualisieren. Knoten „5“ hat also aktualisierte Kosten von 8. Nach Schritt 4,5 sieht es so aus:

Beispiel für Dijkstras Algorithmus

Jetzt hat der Pfad 1-3-7 die Kosten von 8 (bisher). Knoten „7“ wurde nicht als besucht markiert, da wir Knoten „7“ von Knoten „6“ aus erreichen können. Der Weg „1-2-6“ kostete 4. Der Weg 1-2-6-7 kostet also 7.

Da 7 < 8 ist, beträgt der kürzeste Weg vom Quellscheitelpunkt „1“ zum Zielscheitelpunkt „7“ 1-2-6-7 und die Kosten betragen 7. Zuvor waren es 1-3-7 und die Kosten war 8.

Das endgültige Diagramm sieht also folgendermaßen aus:

Beispiel für Dijkstras Algorithmus

Die mit einer schwarzen Linie markierte Kante ist unser kürzester Weg von 1 nach 7 und kostet uns 7.

Pseudocode-Dijkstra-Algorithmus

Hier ist der Pseudocode für Dijkstras Algorithmus

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++-Implementierung Dijkstras Algorithmus

Um den Dijkstra-Algorithmus zu implementieren, verwenden Sie C + +, hier ist der 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);
}

Ausgang:

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-Implementierung des Dijkstra-Algorithmus

Um den Dijkstra-Algorithmus zu implementieren, verwenden Sie python, hier ist der 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)

Ausgang:

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

Wir können sehen, dass der Algorithmus die kürzeste Entfernung vom Quellknoten berechnet.

Anwendung des Dijkstra-Algorithmus

Der Dijkstra-Algo hat eine Vielzahl von Verwendungsmöglichkeiten. Unter anderem wird es häufig im Bereich der Vernetzung eingesetzt. Hier sind einige Beispiele für die praktische Anwendung des Dijkstra-Algorithmus:

Dijkstra auf der Google-Karte: Im Grunde ist dieser Algorithmus das Rückgrat für die Suche nach den kürzesten Wegen. Wie wir aus der obigen Code-Snippet-Ausgabe sehen können.

Anwendung des Dijkstra-Algorithmus

Google verwendet nicht den einfachen Dijkstra-Algorithmus. Stattdessen wird eine modifizierte Version verwendet. Wenn Sie ein Ziel auswählen, werden Ihnen in der Google Map mehrere Routen angezeigt. Unter diesen Pfaden sind einige Pfade für den Benutzer sortiert. Diese ausgewählten Pfade basieren auf der „Zeit“. „Zeit“ ist also ein Randkostenfaktor für den kürzesten Weg.

Dijkstra im IP-Routing: IP-Routing ist eine Netzwerkterminologie. Es bedeutet, wie Ihr Datenpaket über verschiedene Wege zum Empfänger gesendet wird. Diese Pfade bestehen aus Routern, Servern usw. Beim IP-Routing gibt es verschiedene Arten von Protokollen.

Diese Protokolle helfen dem Router, die kürzesten Wege zum Senden der Daten zu finden. Einer der Protokollnamen ist „OSPF (Open Shortest Path First)“. OSPF verwendet den Dijkstra-Algorithmus. Der Router verwaltet eine Routentabelle. Jeder Router shares seine Tabelle mit benachbarten Routern. Nach Erhalt der aktualisierten Tabelle müssen alle Pfade erneut berechnet werden. Zu diesem Zeitpunkt verwendet der Router den Dijkstra-Algorithmus.

Einschränkung des Dijkstra-Algorithmus

Der Dijkstra-Algorithmus kann den kürzesten Weg im negativen Kantendiagramm nicht garantieren. Der Dijkstra-Algorithmus folgt diesen Methoden:

  • Von einem Knoten zum anderen wird ein kürzester Weg genommen.
  • Sobald der kürzeste Weg zwischen zwei Knoten ausgewählt ist, wird dieser nicht erneut berechnet.

Beachten Sie hier zwei Beispiele mit negativen Kanten.

Einschränkung des Dijkstra-Algorithmus

Im linken Diagramm: Es gibt drei Eckpunkte. Dijkstra wird im Diagramm wie folgt ausgeführtwing:

Schritt 1) Der Startscheitelpunkt „1“ wird auf Null initialisiert. Die anderen Knoten haben Unendlichkeit.

Einschränkung des Dijkstra-Algorithmus

Schritt 2) Markieren Sie Knoten „1“ als besucht und fügen Sie ihn in den kürzesten Pfad ein.

Schritt 3) Der Abstand des Quellknotens 1 zu den Knoten „2“ und „3“ ist auf unendlich gesetzt, da der kürzeste Weg noch berechnet werden muss. Daher wird jeder Pfad, der weniger als unendlich kostet, zum kürzesten Pfad hinzugefügt (gieriger Ansatz).

Schritt 4) Aktualisieren des Abstands vom Quellscheitelpunkt oder Quellknoten „1“ auf „2“. Das aktuelle Gewicht beträgt 5 (5

Einschränkung des Dijkstra-Algorithmus

Schritt 5) Wenn wir nun die kürzesten Abstände vom Knoten „1“ überprüfen, stellen wir fest, dass 5 der kürzeste Abstand für Kante 1–> 2 ist. Knoten „2“ wird also als besucht markiert.

Ebenso wird Knoten „3“ ebenfalls als besucht markiert, da die kürzeste Entfernung 3 beträgt.

Wenn wir jedoch beobachten, gibt es einen Pfad 1-3-2, der nur 2 kostet. Aber Dijkstra zeigt, dass von Knoten „1“ zu Knoten „2“ die kürzeste Entfernung 5 beträgt. Dijkstra konnte also nicht die kürzeste berechnen Entfernung richtig. Der Grund dafür ist, dass Dijkstra ein gieriger Algorithmus ist. Sobald ein Knoten als besucht markiert ist, wird er nicht erneut berücksichtigt, obwohl möglicherweise ein kürzerer Pfad verfügbar ist. Dieses Problem tritt nur auf, wenn die Kanten negative Kosten oder Kanten mit negativer Gewichtung aufweisen

Dijkstra kann in diesem Szenario den kürzesten Weg zwischen zwei Knoten nicht berechnen. Daher weist dieser Algorithmus einige Nachteile auf. Um dieses Problem der negativen Kante zu lösen, wird ein anderer Algorithmus namens „Bellman-Ford-Algorithmus“ verwendet. Dieser Algorithmus kann mit negativen Kanten arbeiten.

Dijkstras Algorithmus Complexity

Die obige Implementierung verwendete zwei „for“-Schleifen. Diese Schleifen laufen für die Anzahl der Scheitelpunkte. Also, die Zeit kommtplexität ist O(V2). Hier bedeutet der Begriff „0“ eine Notation, die eine Annahme für den Dijkstra-Algorithmus angibt.

Wir können den Graphen mithilfe der „Priority Queue“ speichern. Eine Prioritätswarteschlange ist eine binäre Heap-Datenstruktur. Es ist effizienter als eine 2D-Matrix. Ein Vorteil, der minimale Kosten verursacht, hat eine hohe Priorität.

Dann ist die Zeit gekommenplexität wird sein O (E log (V)). Dabei ist E die Anzahl der Kanten und V die Anzahl der Eckpunkte.

Die Weltraumkommunikationplexität ist O(V2), da wir eine Adjazenzmatrix verwenden (2D-Array). Space complexDie Funktionalität kann mithilfe einer Adjazenzliste oder einer Warteschlangendatenstruktur optimiert werden.