Floyd-Warshall
Algorithmus für kürzeste Wege zwischen allen Paaren — berechnet den kürzesten Weg zwischen jedem Knotenpaar. Robert Floyd / Stephen Warshall (1962).
Geniale DP-Formulierung: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) für jeden Zwischenknoten k. Drei verschachtelte Schleifen, acht Zeilen Code. Zeitkomplexität: O(V³) — unpraktisch für große Graphen, aber perfekt für unter 200 Knoten.
Treibt Routing-Tabellen in kleinen Netzwerken, transitive Hüllen, "kürzester Handschlag zwischen zwei Personen in einem sozialen Graphen". Kommt mit negativen Gewichten zurecht (aber nicht mit negativen Zyklen). Konkurrent: Johnsons Algorithmus (V·E·logV, besser für dünnbesetzte Graphen).