Lösungsidee

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

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

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


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

jederzeit gilt die Invariante:

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

verbleibende Fragen:

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