Caminos mínimos entre todos los pares

Si hace falta la distancia entre todos los pares de vértices, correr Dijkstra desde cada uno es una opción razonable. Pero hay un algoritmo de tres ciclos anidados y cinco líneas que resuelve lo mismo, incluso con pesos negativos, y su idea central se explica en una frase.

Programación dinámica sobre los intermedios permitidos

Floyd-Warshall es programación dinámica sobre qué vértices se permiten como intermedios. El estado es: la mejor distancia de $i$ a $j$ usando sólo los primeros $k$ vértices como escalas.

Al habilitar el vértice $k$, para cada par hay dos opciones: el camino no lo usa y queda igual, o lo usa y se parte en dos tramos que ya están calculados:

Tres ciclos, y un orden que no se puede alterar

Eso se escribe como tres ciclos sobre una matriz, y hay un orden que no se puede alterar: el ciclo de $k$ va afuera, y los de $i$ y $j$ adentro. Con $k$ adentro, el algoritmo mezcla estados de distintas etapas y da resultados incorrectos.

La otra sutileza es que no hace falta mantener dos matrices, una por etapa. Actualizar sobre la misma es correcto, porque la fila y la columna $k$ no cambian durante la iteración $k$: ese detalle es lo que reduce la memoria a $\Theta(V^2)$.

Cuándo conviene contra correr Dijkstra V veces

El costo es $\Theta(V^3)$ pase lo que pase, sin importar cuántas aristas haya. La comparación con correr Dijkstra $V$ veces —$O(V\,E\log V)$— depende de la densidad: en grafos densos Floyd-Warshall gana, en ralos pierde.

Lo que siempre gana es en simplicidad y en constantes: es una matriz y tres ciclos sobre memoria contigua, sin colas de prioridad ni listas de adyacencia.

Pesos negativos y ciclos, leídos en la diagonal

Acepta pesos negativos sin cambios, cosa que Dijkstra no. Y detecta ciclos negativos con una lectura: si algún elemento de la diagonal quedó menor que cero, hay un ciclo que vuelve al mismo vértice con costo negativo.

Si hay ciclos negativos, el resto de los valores deja de tener sentido y conviene cortar ahí. La alternativa cuando el grafo es ralo y tiene negativos es Johnson: reetiqueta los pesos con Bellman-Ford para volverlos no negativos y después corre Dijkstra desde cada vértice.

Reconstruir el camino, no sólo la distancia

Para reconstruir los caminos, y no sólo las distancias, se lleva una segunda matriz con el próximo salto —o el vértice intermedio— de cada par, que se actualiza junto con la distancia.

Reconstruir un camino es después seguir esa matriz salto a salto. Cuesta lo que mide el camino, y evita guardar $V^2$ listas completas.

El mismo esquema para otras preguntas

El mismo esquema resuelve otras preguntas cambiando la operación. Con o lógico en vez de suma y mínimo, calcula la clausura transitiva: qué vértices son alcanzables desde cuáles, que es el algoritmo de Warshall.

Con máximo y mínimo da el camino de cuello de botella —la mayor capacidad mínima entre dos puntos—. Es el mismo recorrido de estados con otro semianillo, y sirve para redes de capacidad o rutas de confiabilidad.

Cuándo Floyd-Warshall y cuándo Dijkstra n veces

Lo que preguntan sobre esto

Cierre

Floyd-Warshall pregunta, para cada par y cada vértice nuevo habilitado, si pasar por ahí mejora. Con $k$ en el ciclo externo da todas las distancias en $\Theta(V^3)$ y $\Theta(V^2)$ de memoria, acepta pesos negativos, detecta ciclos negativos en la diagonal y se adapta a otras preguntas cambiando las operaciones.