Lösungsidee

iterativer Algorithmus mit Zustand d : V→$\mathbb {R}$∪{ + ∞}.

d (s) : = 0,∀x≠s : d (x) : = + ∞ 

while es gibt eine Kante 
i$\;\stackrel{{w_{i,j}}}{\to}\;$j mit 
d (i) + wi, j < d (j) 


d (j) : = d (i) + wi, j

jederzeit gilt die Invariante:

• ∀x∈V: es gibt einen Weg von s nach x mit Gewicht d (x)
• ∀x∈V : D(x)≤d (x).

verbleibende Fragen:

• Korrektheit (falls Termination)
• Auswahl der Kante (aus mehreren Kandidaten)
• Termination, Laufzeit