algorithm sssp:= ; dis[s]:=0; initialisiere eine Priorityqueue PQ, die
alle Knoten enthält mit Schlüssel dis;for alle do
from[v]:=s
od
while do
v:= ExtractMin(PQ);
; for alle , d do
if dis then
DecreaseKey(w, dis[v] + d(v, w));
co DecreaseKey verändert dis[w] oc
from[w]:= v;
fi
od
od
Seien n=|V| und m:= Anzahl wirklicher Kanten:
Laufzeit (mit Fibonacci-Heaps):
Initialisierung: | |
ExtractMin : | |
---|---|
Sonstiger Aufwand: | (z.B. DecreaseKey ) |
Beispiel für Dijkstra-Algorithmus: