Der Dijkstra-Algorithmus ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Diagramm zu lösen. Dies bedeutet, dass der Dijkstra-Algorithmus bei einer Anzahl von Knoten und den Kanten zwischen ihnen sowie der “Länge” der Kanten (als “Gewicht” bezeichnet) den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten findet.

Beschreibung des Algorithmus

Das Grundprinzip des Dijkstra-Algorithmus besteht darin, den Knoten mit dem derzeit kleinsten Abstand zur Quelle iterativ zu betrachten und alle noch nicht besuchten Nachbarn zu aktualisieren, wenn der Pfad zu ihm über den aktuellen Knoten kürzer ist. Im Einzelnen führt dies zu den folgenden Schritten:

1. Initialisieren Sie den Abstand zum Startknoten als 0 und den Abstand zu allen anderen Knoten als unendlich
2. Setzen Sie alle Knoten auf “nicht besucht”.

3. Während wir nicht alle Knoten besucht haben:

   1. Suchen Sie den Knoten mit der aktuell kürzesten Entfernung von der Quelle (beim ersten Durchgang ist dies der Quellknoten selbst).
   2. Überprüfen Sie für alle Knoten daneben, die wir noch nicht besucht haben, ob die derzeit kleinste Entfernung zu diesem Nachbarn größer ist, als wenn wir über den aktuellen Knoten gehen würden
   3. Wenn dies der Fall ist, aktualisieren Sie die kleinste Entfernung dieses Nachbarn auf die Entfernung von der Quelle zum aktuellen Knoten plus die Entfernung vom aktuellen Knoten zu diesem Nachbarn

Am Ende enthält das Array, mit dem wir die aktuell kürzeste Entfernung von der Quelle zu allen anderen Knoten verfolgt haben, die (endgültigen) kürzesten Entfernungen.

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm:

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

1. Besuche Knoten 0
2. Aktualisieren der Entfernung von Knoten 1 bis 3
3. Aktualisieren des Abstands von Knoten 2 zu 1
4. Besuchte Knoten: 0
5. Derzeit niedrigste Entfernungen: [0, 3, 1, unendlich, unendlich, unendlich]

6. Besuch von Knoten 1 mit der aktuellen Entfernung 1

   • Aktualisieren der Entfernung von Knoten 3 bis 5
   • Besuchte Knoten: 0, 2
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, unendlich, unendlich]

7. Besuch von Knoten 3 mit der aktuellen Entfernung 3

   • Aktualisieren der Entfernung von Knoten 4 bis 4
   • Besuchte Knoten: 0, 1, 2
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, 4, unendlich]

8. Besuche Knoten 4 mit der aktuellen Entfernung 4

   • Aktualisieren der Entfernung von Knoten 5 bis 5
   • Besuchte Knoten: 0, 1, 2, 4
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, 4, 5]

9. Besuche Knoten 5 mit aktueller Entfernung 5

   • Keine zu aktualisierenden Entfernungen
   • Besuchte Knoten: 0, 1, 2, 3, 4
   • Derzeit niedrigste Entfernungen: [0, 3, 1, 5, 4, 5]

10. Besuch des Knotens 5 mit der aktuellen Entfernung 5

    • Keine zu aktualisierenden Entfernungen
    • Besuchte Knoten: 0, 1, 2, 3, 4, 5

Alle besuchten Knoten Letzte niedrigste Abstände: [0, 3, 1, 5, 4, 5]

Laufzeit des Algorithmus

Die Laufzeitkomplexität von Dijkstra hängt davon ab, wie es implementiert wird. Wenn ein Min-Heap verwendet wird, um den nächsten zu besuchenden Knoten zu bestimmen, und die Adjazenz unter Verwendung von Adjazenzlisten implementiert wird, ist die Laufzeit O(| E | + | V | log | V|) (|V| = Nummer Anzahl der Knoten, |E| = Anzahl der Kanten). Wenn wir einfach alle Entfernungen durchsuchen, um den Knoten mit der niedrigsten Entfernung in jedem Schritt zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(| V | ^ 2).

Speicherkomplexität des Algorithmus

Die Speicherkomplexität von Dijkstra hängt auch davon ab, wie es implementiert ist, und entspricht der Laufzeitkomplexität.