Nächste Seite: Laufzeit Aufwärts: (Integer/Real) Difference Logic Vorherige Seite: Kürzeste Wege in Graphen

Lösungsidee

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

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

while es gibt eine Kante 
ij
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