Dijkstras Algorithmus in Python & C++ (Beispiel)

Was ist der kürzeste Weg bzw. die kürzeste Entfernung?

Der kürzeste Weg von einem Startknoten zu einem Zielknoten ist der Weg mit den geringsten Kosten. In der Graphentheorie gibt es mehrere Wege von einem Startknoten zu einem Zielknoten. Wenn einer dieser Wege die geringsten Kosten aufweist, nennen wir ihn den kürzesten Weg.

Hier bezeichnet „Kosten“ die Anzahl der Knoten im Pfad oder die Summe der Kosten aller Kanten. Ein Pfad kann eine oder mehrere Kanten enthalten. Die Verbindung zwischen zwei Knoten wird als „Kante“ bezeichnet. Es gibt verschiedene Algorithmen zur Berechnung kürzester Pfade, wie beispielsweise den Dijkstra-Algorithmus und den Bellman-Ford-Algorithmus.

Hier besprechen wir den Dijkstra-Algorithmus. Betrachten wir dazu den folgenden gewichteten Graphen:

Ein ungerichtet-gewichteter Graph

• Der Begriff „gewichtet“ bezeichnet die Kosten für den Wechsel von einem Knoten zu einem anderen. Beispielsweise betragen die Kosten bzw. das Gewicht für den Wechsel von Knoten 1 zu Knoten 2 1.
• Der Pfad zwischen Knoten 1 und Knoten 2 wird als Kante bezeichnet.
• „Ungerichtet“ bedeutet, dass man von einem Knoten zu einem anderen und zurück zum vorherigen Knoten gelangen kann. Wenn wir also alle Routen von Knoten 1 zu Knoten 7 finden wollen, lauten diese:

Unter diesen vier Routen können wir sehen, dass die erste Route 7 kostet. Sie ist also der kürzeste Weg in Bezug auf die Kosten.

Kürzester Weg

Wie Dijkstras Algorithmus funktioniert

Der Dijkstra-Algorithmus findet die kürzeste Entfernung in gerichteten und ungerichteten gewichteten Graphen. Er ist gierig, da er stets den kürzesten oder nächstgelegenen Knoten vom Ursprung auswählt. „Gierig“ bedeutet, dass der Algorithmus aus einer Menge von Ergebnissen das beste auswählt.

Hier suchen wir die kürzesten Wege unter allen Routen. Der Dijkstra-Algorithmus findet also alle kürzesten Wege von einem einzigen Startknoten aus. Daher verhält er sich wie ein Gieriger Algorithmus.

Im folgenden Abschnitt „Beispiel“ finden Sie die schrittweise Vorgehensweise. Sie funktioniert wie folgt:

Schritt 1) Initialisiere den Startknoten mit Kosten von 0 und die restlichen Knoten mit Kosten von unendlich.
Schritt 2) Verwenden Sie ein Array oder eine Liste, um die wichtigsten Informationen zu speichern. track der besuchten Knoten.
Schritt 3) Aktualisieren Sie die Knotenkosten mit den minimalen Kosten. Dies kann durch Vergleich der aktuellen Kosten mit den Pfadkosten erfolgen (wie im Beispielabschnitt gezeigt).
Schritt 4) Fahren Sie mit Schritt 3 fort, bis alle Knotenpunkte besucht wurden.

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 ein Algorithmus zur Suche kürzester Pfade ist, während BFS und DFS allgemeine Pfadfindungsalgorithmen sind. Im Allgemeinen berücksichtigen BFS und DFS bei der Pfadfindung nicht die Kantenkosten. Daher können diese Algorithmen nicht den kürzesten Pfad garantieren.

Demonstration der Funktionsweise der Breitensuche in einem 2D-Gitter

Algoskizze, zeigt 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.

Betrachten wir ein Beispieldiagramm:

Hier findet die Breitensuche (BFS) einen Pfad in Ebene 2. Die BFS durchläuft den Graphen in Ebenenreihenfolge. Der Ablauf ist also folgender:

Schritt 1) Beginne bei Knoten „1“ und besuche alle benachbarten Knoten 2, 3, 4.

Schritt 2) Markiere die Knoten 2, 3 und 4 als Ebene 1 und besuche ihre benachbarten Knoten. Die Erkundung aller benachbarten Knoten wird fortgesetzt, bis der Zielknoten erreicht ist.

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 die Pfadkosten anhand der Anzahl der Kanten. DFS geht dabei wie folgt vor:

• 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.

Der Dijkstra-Algorithmus wählt Kanten jedoch anhand ihrer Kosten aus. Als Greedy-Algorithmus wählt er die Pfade mit den geringsten Kosten.

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.

Der Dijkstra-Algorithmus findet die kürzesten Wege durch die Berechnung von Gewichtungen. Er durchsucht nicht alle möglichen Wege. Betrachten wir ein Beispiel: Angenommen, Sie sollen den kürzesten Weg von Knoten 1 zu Knoten 7 finden.

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

Schritt 1) Setze die Kosten des Startknotens auf 0. Weise zu „Inf“ zu den übrigen Knoten. Das bedeutet, dass kein Pfad zwischen der Quelle und dem Knoten existiert oder dass der Pfad noch nicht besucht wurde.

Schritt 2) Wenn Sie Knoten 1 auswählen, wird dieser als besucht markiert. Aktualisieren Sie anschließend alle benachbarten Knoten von Knoten 1. 2, 3 und 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. Angenommen, wir befinden uns bei Knoten 1 und müssen die Kosten der benachbarten Knoten 2, 3 und 4 aktualisieren. Nach der Aktualisierung sehen die Kosten wie folgt aus:

Schritt 3) Für Knoten „2“ sind die Nachbarn 6 und 3. Wir aktualisieren die Kosten für Knoten „6“, indem wir den aktuellen Wert (unendlich) mit den Kosten von Knoten 2 plus den Pfadkosten von 2 nach 6 vergleichen. Vereinfacht gesagt, hat Knoten „6“ die Kosten 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 ist der Nachbarknoten 7. Wir vergleichen den aktuellen Wert von Knoten 7 mit den Pfadkosten (7+1) bzw. 8 und aktualisieren die Kosten von Knoten 7. Diese betragen 8. Somit finden wir einen Pfad von Knoten 1 zu Knoten 7: 1→3→7. Die Kosten betragen 8.

Schritt 5) Für Knoten 4 aktualisieren wir die Kosten der benachbarten Knoten entsprechend. Knoten „5“ hat somit aktualisierte Kosten von 8. Nach den Schritten 4 und 5 sieht es folgendermaßen aus:

Der Pfad 1-3-7 hatte bisher Kosten von 8. Knoten „7“ wurde nicht als besucht markiert, da er von Knoten „6“ aus erreichbar ist. Der Pfad „1-2-6“ hatte Kosten von 4. Daher hat der Pfad 1-2-6-7 Kosten von 7.

Da 7 < 8, ist der kürzeste Pfad vom Startknoten „1“ zum Zielknoten „7“ der Weg 1-2-6-7, und die Kosten betragen 7. Zuvor war er der Weg 1-3-7, und die Kosten betrugen 8. Der endgültige Graph 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.

Spitzname Code Dijkstras Algorithmus

Hier ist der Pseudocode für den Dijkstra-Algorithmus:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Implementierung des Dijkstra-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] && 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] && graph[U][j] &&
          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 PythonHier 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] <= _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 < 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-Algorithmus hat ein breites Anwendungsgebiet. Unter anderem findet er weite Verbreitung im Bereich der Netzwerktechnik. Hier einige Beispiele für praktische Anwendungen des Dijkstra-Algorithmus:

Dijkstra in Google Landkarten: Dieser Algorithmus ist die Grundlage für die Suche nach den kürzesten Wegen, wie wir aus der Ausgabe des obigen Code-Ausschnitts sehen können.

Google Es verwendet nicht den einfachen Dijkstra-Algorithmus, sondern eine modifizierte Version. Wenn Sie ein Ziel auswählen, werden Ihnen mehrere Pfade angezeigt. Google Karten. Unter diesen Pfaden werden einige für den Benutzer vorsortiert. Diese Pfade werden anhand der „Zeit“ ausgewählt. Die „Zeit“ stellt also die Kantenkosten für den kürzesten Pfad dar.

Dijkstra im IP-Routing: IP-Routing IP-Routing ist ein Begriff aus der Netzwerktechnik. Er beschreibt, wie Ihr Datenpaket über verschiedene Wege zum Empfänger gesendet wird. Diese Wege bestehen aus Routern, Servern und anderen Geräten. Beim IP-Routing gibt es verschiedene Protokolltypen.

Diese Protokolle helfen dem Router, die kürzesten Wege für die Datenübertragung zu finden. Eines dieser Protokolle ist OSPF (Open Shortest Path First). OSPF verwendet den Dijkstra-Algorithmus. Der Router verwaltet eine Routentabelle und teilt diese mit seinen Nachbarroutern. Nach Erhalt der aktualisierten Tabelle müssen die Router alle Wege neu berechnen. Dabei kommt der Dijkstra-Algorithmus zum Einsatz.

Einschränkung des Dijkstra-Algorithmus

Der Dijkstra-Algorithmus kann in einem Graphen mit negativen Kanten keinen kürzesten Pfad garantieren. Der Dijkstra-Algorithmus basiert auf folgenden Prinzipien:

• 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. Der Dijkstra-Algorithmus wird auf dem Graphen wie folgt ausgeführt:

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

Schritt 2) Markiere Knoten „1“ als besucht und nimm ihn in den kürzesten Pfad auf.

Schritt 3) Die Entfernung des Startknotens 1 zu den Knoten „2“ und „3“ wird auf unendlich gesetzt, da der kürzeste Pfad noch nicht berechnet wurde. Daher wird jeder Pfad, dessen Kosten kleiner als unendlich sind, dem kürzesten Pfad hinzugefügt (gieriger Ansatz).

Schritt 4) Die Distanz vom Quellknoten „1“ zu „2“ wird aktualisiert. Das aktuelle Gewicht beträgt 5 (5 < ∞). Analog wird die Distanz vom Knoten „1“ zu „3“ mit dem Gewicht 3 aktualisiert.

Schritt 5) Wenn wir nun die kürzesten Entfernungen von Knoten „1“ überprüfen, stellen wir fest, dass die kürzeste Entfernung für die Kante 1→2 5 beträgt. Daher wird Knoten „2“ als besucht markiert. Ebenso wird Knoten „3“ als besucht markiert, da die kürzeste Entfernung 3 beträgt.

Betrachtet man jedoch genauer, so gibt es einen Pfad 1-3-2, der nur 2 kostet. Dijkstra zeigt aber an, dass die kürzeste Distanz von Knoten „1“ zu Knoten „2“ 5 beträgt. Dijkstra hat die kürzeste Distanz also nicht korrekt berechnet. Der Grund dafür ist, dass Dijkstra ein Greedy-Algorithmus ist. Sobald ein Knoten als besucht markiert wurde, wird er nicht erneut betrachtet, selbst wenn ein kürzerer Pfad existiert. Dieses Problem tritt nur auf, wenn Kanten negative Kosten oder negatives Gewicht haben.

Der Dijkstra-Algorithmus kann in diesem Szenario den kürzesten Pfad zwischen zwei Knoten nicht berechnen. Daher weist er einige Nachteile auf. Um dieses Problem mit negativen Kanten zu lösen, wird der Bellman-Ford-Algorithmus verwendet. Dieser Algorithmus kann auch 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(V²)Hierbei handelt es sich bei dem Begriff „O“ um eine Notation, die eine Annahme für den Dijkstra-Algorithmus angibt.

Wir können den Graphen mithilfe einer Prioritätswarteschlange speichern. Eine Prioritätswarteschlange ist eine binäre Heap-Datenstruktur. Sie ist effizienter als eine zweidimensionale Matrix. Eine Kante mit minimalen Kosten erhält eine hohe Priorität. Die Zeitkomplexität beträgt dann O(E log V). Dabei ist E die Anzahl der Kanten und V die Anzahl der Eckpunkte.

Die Raumkomplexität ist O(V²), da wir eine Adjazenzmatrix verwenden (2D-Array). Die Speicherkomplexität kann durch die Verwendung einer Adjazenzliste oder einer Warteschlangen-Datenstruktur optimiert werden.

Häufig gestellte Fragen