Floyd-Warshall
Algoritmo dei cammini minimi tra tutte le coppie: calcola il percorso più breve tra ogni coppia di nodi. Robert Floyd e Stephen Warshall (1962).
Formulazione elegante di programmazione dinamica: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) per ogni nodo intermedio k. Tre cicli annidati, otto righe di codice. Complessità temporale O(V³): impraticabile su grafi grandi, ma perfetto sotto i 200 nodi circa.
Serve per le tabelle di routing di piccole reti, la chiusura transitiva e il «percorso di conoscenze più breve tra due persone in un grafo sociale». Gestisce pesi negativi (ma non cicli negativi). Concorrente: l'algoritmo di Johnson (V·E·logV, migliore sui grafi sparsi).