Dijkstra's Algorithmus

$\parbox{70mm}{ \textbf{Gegeben:} $G=(V,A), (A=V \times V),$\space Dis... ...p\{+\infty\}$. Startknoten $s$. $G$\space durch Adjazenzlisten dargestellt.\\ }$

algorithm sssp:=

$\ulcorner$$S:=\{s\}$; dis[s]:=0; initialisiere eine Priorityqueue PQ, die
alle Knoten  $v\in V\setminus\{s\}$ enthält mit Schlüssel dis$[v]:=\text{d}(s,v)$;for alle $v \in V-\{s\}$ do
		 from[v]:=s
od
while $S \neq V$ do
		 v:=    ExtractMin(PQ);
		 $S:= S \cup \{v\}$;		 for alle $w \in V-S$, d$(v,w)<\infty$ do
		 		 if dis$[v] + \text{d}(v,w) < \text{dis}[w]$ then
		 		 		    DecreaseKey(w, dis[v] + d(v, w));
		 		 		 		 co    DecreaseKey verändert dis[w] oc
		 		 		 from[w]:= v;
		 		 fi
		 od
od
$\llcorner$ 

Seien n=|V| und m:= Anzahl wirklicher Kanten:

Laufzeit (mit Fibonacci-Heaps):

$$\mathcal{O}(n)$$ Initialisierung:

$$n \cdot \mathcal{O}(\log n)$$

$$m-\mathcal{O}(1)$$ Sonstiger Aufwand:

$\Rightarrow$ Zeitbedarf also:

Korrektheit: Wir behaupten, daß in dem Moment, in dem ein $v \in V-\{s\}$Ergebnis der FindMin Operation ist, der Wert dis[v] des Schlüssels von v gleich der Länge eines kürzesten Pfades von s nach v ist.

Beweis: durch Widerspruch: Sei $v \in V-\{s\}$ der erste Knoten, für den diese Behauptung nicht stimmt und sei

ein kürzester Pfad von s nach v, mit einer Länge $< \text{dis}[v]$. Dabei sind $s_1,\ldots,s_r\in S$, $v_1 \notin S$ [r=0 und/oder q=0 ist möglich]. Betrachte Pfad

; seine Länge ist $< \text{dis}[v]$, für $q\geq 1$ (ebenso für q=0) ist also dis$[v_1] <\text{dis}[v]$, Widerspruch zur Wahl von v. $\Diamond$

Beispiel für Dijkstra-Algorithmus:

Beobachtung:

• ExtractMin liefert eine monoton steigende Folge von Schlüsseln dis[ ];
• Die Schlüssel in PQ sind stets $\leq$ dis[v]+C, wobei v das Ergebnis der vorangehenden ExtractMin -Operation (bzw. s zu Beginn) und $C:=\max_{u,v\in A}\{d(u,v)\}$ ist.

Bemerkung:

1.

Verwendet man Dijkstra's Algorithmus mit d-Heaps, so erhält man Laufzeit

2.

Mikkel Thorup (STOC '98):