Algorithmen brutal – Bellmann-Ford-Algorithmus für beliebige Kantengewichte

Allgemeines Korrektheitskriterium

Zyklische Graphen (10.2 im Buch)

Von überall nach überall

Kürzeste Wege: Zusammenfassung

Straßennetzwerke

Ideen für Routenplanung

Beispiel

Transit-Node Routing

Kap. 11: Minimale Spannbäume

Minimale Spannbäume (MST)

Minimale spannende Wälder (MSF)

Anwendungen

MST-Kanten auswählen und verwerfen

Der Jarnik-Prim-Algorithmus

Analyse

Kruskals Algorithmus (1956)

Kruskals Algorithmus – Korrektheit

Union-Find Datenstruktur

Union-Find Datenstruktur – Erste Version

Pfadkompression

Union by Rank

Analyse – nur Union by rank

Analyse – Pfadkompression + Union by rank