Lösungsidee

iterativer Algorithmus mit Zustand d : V$\to$$\mathbb {R}$ $\cup$ { + $\infty$}.

d (s) : = 0,$\forall$x $\neq$ s : d (x) : = + $\infty$ 

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:

• $\forall$x $\in$ V: es gibt einen Weg von s nach x mit Gewicht d (x)
• $\forall$x $\in$ V : D(x)$\le$d (x).

verbleibende Fragen:

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