Starten

Allgemeine Definition

Kante (u,v) relaxieren

Dijkstras Algorithmus

Beispiel

Korrektheit

v erreichbar ->

v gescannt ->

Dijkstra: Implementierung?

Prioritätsliste

Imlementierung

Beispiel

Dijkstra: Laufzeit

Analyse im Mittel

Monotone ganzzahlige Prioritätslisten

Negative Kosten

Zurück zu Basiskonzepten

Allgemeines Korrektheitskriterium

Algorithmen brutal Bellman-Ford-Algorithmus für beliebige Kantengewichte

Negative Kreise finden

Beispiel

Bellmann-Ford – Laufzeit

Azyklische Graphen

Von überall nach überall

Kürzeste Wege: Zusammenfassung