Input: Ein gerichteter Graph $G=(V,E)$, ein Startvertex $s \in V$ und eine nicht-negative Länge $l_e$ für jeder Kante $e \in E$.
Output: $dist(s,v)$ für jeden Knoten $v \in V$.
Gegeben sei $G = (V,E)$ mit
Welche Werte haben die Längen $dist(a,v)$ für $v=\{a, b,c,d\}$?
Dijkstra¶Input: directed graph $G=(V,E)$ in adjacency-list representation, a vertex $s \in V$, a length $l_e$ for each edge $e \in E$
Postcondition: for every vertex $v \in V$ a length $l(v)$ equals to the true shortest path distance $dist(s,v)$
$X := \{s\}$
$len(s)=0$, $len(v)=\infty$ for each $v\neq s$
while there is an edge $(v,w)$ mit $v \in X, w \notin X$ do
$(v^*, w^*):=$ such an edge minimizing $len(v)+l_{vw}$
add $w^*$ to $X$
$len(w^*):=len(v^*)+l_{v^*w^*}$
Für jeden direkten Graphen $G=(V,E)$ und jeden Startknoten $s$ und für alle möglichen, nicht-negativen Werte der Kantenlängen ist nach Abschluss der Dijkstra Algorithmus $len(v) = dist(s,v)$ für jeden Knoten $v \in V$.
Beweis durch vollständige Induktion, dass Dijkstra nicht längere Distanzen als die wahre kürzeste berechnet:
Weg zum Startknoten $s$ kann nie kürzer werden als $0$, da keine negativen Kanten erlaubt sind.
Bei jedem weiteren Schritt der Induktion gilt, dass die bereits durch Dijkstra erkundeten Knoten (in $X$) korrekte Länge haben, d.h. $len(v')=dist(s, v')$.
In jedem weiteren Schritt wird ein neuer Knoten $w^*$ mit Eintrag $len(w^*)$ erkundet, wenn die Kante von $v^*$ zu $w^*$ den minimalen Wert $len(v^*)+l_{v^*w^*}$ hat für beliebige bereits erkundete $v^*$, d.h. $len(w^*) = len(v^*) + l_{v^*w^*}$.
Für die Weglänge aller möglichen Wege von $s$ zu $w^*$ (eventuell) über einen noch nicht erkundeten Knoten $z$ (mit $v'$ ist ein bereits erkundeter Knoten) gilt (mit $len(v')=dist(s, v')$:
Streng genommen muss man zusätzlich auch noch zeigen, dass Dijkstra nicht zu kurze Distanzen berechnet.
Welche Laufzeit (in $n$ und $m$) hat eine direkte (straightforward) Implementation des Dijkstra-Algorithmus?
d.h. $\Rightarrow O(mn)$
Für jeden gerichteten Graphen $G(V, E)$ und jeden Startknoten $s$ benötigt die direkte (straightforward) Implementation des Dijkstra-Algorithmus eine Laufzeit von $O(nm)$ mit $m=|E|$ und $n=|V|$.
Für eine bessere (lineare) Laufzeit benötigen wir keinen anderen Algorithmus, sondern eine geeignete Datenstruktur, um die Kante zu finden, die die minimale Länge $len(v)+l_{vw}$ hat.
Dies ist ein Beispiel für das Zusammenspiel zwischen Algorithmen und Datenstrukturen.
Im nächsten Kapitel behandeln wir diese Datenstruktur: den Heap.
Wie muss Dijkstra erweitert werden, sodass man von einem von $s$ erreichbaren Knoten $a$, den Pfad von $s$ zu $a$ erhalten (z.B. als Liste der Kanten) kann.