Dijsktras Algorithmus: C++, Python Codebeispiel
Sarah Chen
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 auf der Route oder die Summe der Kosten auf jedem Pfad. Ein Pfad kann eine oder mehrere Kanten haben. Die Verbindung zwischen zwei Knoten wird als „Kante“ bezeichnet. Es gibt verschiedene Arten von Algorithmen für kürzeste Pfade, wie den Dijkstra-Algorithmus, den Bellman-Ford-Algorithmus usw.
Hier diskutieren wir über den Dijkstra-Algorithmus
Schauen wir uns das folgende gewichtete Diagramm an:
- 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.
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 Algorithmus zur kürzesten Pfadfindung ist, während 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 Pfad garantieren.
2D-Gitterdemonstration der Funktionsweise von BFS
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:
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 durchlaufen:
- 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 folgende Aktionen aus:
- 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.
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.
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:
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:
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.
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:
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:
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 Dijkstras 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.
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 Pfade 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 teilt seine Tabelle mit benachbarten Routern. Nach Erhalt der aktualisierten Tabelle müssen sie alle Pfade erneut berechnen. 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.
Im linken Diagramm: Es gibt drei Knoten. Dijkstra wird auf dem Graphen wie folgt ausgeführt:
Schritt 1) Der Startscheitelpunkt „1“ wird auf Null initialisiert. Die anderen Knoten haben Unendlichkeit.
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
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.
Komplexität des Dijkstra-Algorithmus
Die obige Implementierung verwendet zwei „for“-Schleifen. Diese Schleifen werden für die Anzahl der Knoten ausgeführt. Die zeitliche Komplexität beträgt also 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 beträgt die Zeitkomplexität O (E log (V)). Dabei ist E die Anzahl der Kanten und V die Anzahl der Eckpunkte.
Die Raumkomplexität ist O(V2), da wir eine Adjazenzmatrix verwenden (2D-Array). Die Speicherkomplexität kann durch die Verwendung einer Adjazenzliste oder einer Warteschlangen-Datenstruktur optimiert werden.
