Floyd-Warshall
Algoritmo de caminos más cortos entre todos los pares — calcula el camino más corto entre cada par de nodos. Robert Floyd / Stephen Warshall (1962).
Una formulación de programación dinámica muy elegante: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) para cada nodo intermedio k. Tres bucles anidados, 8 líneas de código. Complejidad temporal O(V³) — poco práctico para grafos grandes pero perfecto para menos de 200 nodos.
Se usa en tablas de rutas de redes pequeñas, en el cierre transitivo, o para calcular "el saludo más corto entre dos personas en un grafo social". Admite pesos negativos (pero no ciclos negativos). Competencia: el algoritmo de Johnson (V·E·logV, mejor en grafos dispersos).