Algorithmus von Dijkstra

Lemma: (Idee)
Führt ein kürzester Pfad von $u$ über $w$ nach $v$, so sind die beiden Teilpfade $u$ bis $w$ sowie $w$ bis $v$ ebenfalls kürzeste Pfade.

Algorithmus:
Der Algorithmus von Dijkstra löst das SSSP-Problem, folgende Initialisierung:
- $W$: Liste der Knoten mit bekanntem kürzesten Weg vom Startknoten $s$, zu Beginn $W=s$
- $\rho[v]$: Gewicht (Entfernung von $s$) an jedem Knoten $v$, zu Beginn je $+\inf$
- $pred[v]$: Vorgängerknoten auf dem kürzesten Weg von $s$ nach $v$
Zunächst wird ein fertiger Knoten $u \in W$ mit minimalem Gewicht (Prioritätswarteschlange) gewählt. Für alle Nachbarn $v$ von $u$ wird deren Gewicht herabgesetzt, wenn $\rho[u]+d(u,v)$ (also der Weg über $u$) kleiner ist. Außerdem wird dann $pred[v]=u$ festgehalten und $u$ in $W$ aufgenommen. Dann ist erneut das minimale $u$ zu wählen, bis der Zielknoten $z$ erreicht oder alle Knoten in $W$ sind. Kürzester Weg ist dann $pred[pred[...pred[z]]]$.

Komplexität:
Der Algorithmus von Dijkstra benötigt für $n$ Knoten und $m$ Kanten die Zeit $O(n+m)$, wenn alle Operationen der Prioritätswarteschlange in Zeit $O(1)$ ausführbar sind. Es werden bis zu je $n$ ExtractMin und Insert, und bis zu $m$ DecreaseKey Aufrufe benötigt:
- mit Fibonacci Heap: $O(n \log n + m)$
- mit $2$-level Buckets: $O(n \sqrt{C} + m)$
- mit Radix Heaps: $O(n \log(C) + m)$

Bemerkungen:
- Es lässt sich zeigen, dass das SSSP-Problem in Zeit $O(n+m)$ lösbar ist [Thorup].
- Der Algorithmus von Dijkstra funktioniert a priori nur auf positiven Kantengewichten. Bei negativen Gewichten ist eine Rekalibrierung [Johnson] nötig: es wird ein zusätzlicher Knoten $s$ eingefügt und mit allen Knoten über Kantengewicht 0 verbunden, dann über Bellmann-Ford der negativste Pfad $p$ von $s$ zu irgendeinem $v$ bestimmt und alle Kanten um $p$ erhöht/angepasst (sinnvoll nur für APSP).
- Anwendung eines optimalen SSSP-Algorithmus löst das APSP-Problem in $O(n(n+m)).$