El algoritmo de Floyd–Warshall

Los viejos atlas de carreteras tenían una tabla al final: la distancia entre cada par de ciudades. Floyd–Warshall es una forma de calcular esa tabla, y es uno de los algoritmos más cortos que se han escrito: tres bucles, una comparación, y cada distancia más corta encaja en su sitio.

Un grafo pequeño cuyas aristas tienen longitudes, junto a una tabla de distancias entre cada par de nodos, con una fila y una columna resaltadas
Un grafo pequeño cuyas aristas tienen longitudes, junto a una tabla de distancias entre cada par de nodos, con una fila y una columna resaltadas

La idea

El algoritmo de Dijkstra y Bellman–Ford encuentran las distancias más cortas desde un solo origen. Floyd–Warshall las encuentra de cada nodo a todos los demás a la vez, en una tabla con una fila y una columna por nodo. Empieza con lo que dicen directamente las aristas y luego mejora toda la tabla admitiendo cada vez más nodos como escalas en el camino.

Paso a paso

Llena la tabla: 0 de cada nodo a sí mismo, la longitud de la arista entre vecinos e infinito en lo demás. Luego, para cada nodo k y para cada par i, j: si la distancia de i a k más la distancia de k a j es menor que la distancia de i a j, escribe el número menor. Ese es todo el algoritmo. En código son tres bucles, con k por fuera.

Un ejemplo

Toma cuatro nodos con las aristas A–B de longitud 3, B–C 1, A–C 5 y C–D 2. La tabla empieza con ellas, e infinito para A–D y B–D. La ronda A no cambia nada, porque todo camino por A es más largo. La ronda B encuentra de A a C pasando por B: 3 + 1 = 4, menos que 5. La ronda C encuentra de A a D pasando por C: 4 + 2 = 6, y de B a D: 1 + 2 = 3, los dos primeros caminos encontrados. La ronda D no cambia nada. La tabla final: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Por qué importa el orden de los bucles

La escala k debe ser el bucle exterior. Tras la ronda de k, cada casilla es la distancia más corta usando como escalas solo los k primeros nodos, y la siguiente ronda se apoya en eso: un mejor camino por la nueva escala es un mejor camino hasta ella más un mejor camino desde ella, ambos ya correctos. Poner k en un bucle interior rompe esa garantía y puede dejar distancias erróneas. Actualizar la tabla sobre la marcha durante una ronda es seguro, porque la fila y la columna de k no cambian en esa ronda.

Historia y usos

Bernard Roy describió el método en 1959. En 1962 Stephen Warshall lo publicó para el cierre transitivo, que solo pregunta si un nodo puede llegar a otro, y Robert Floyd lo publicó para caminos más cortos. Calcula tablas de distancias y tablas de enrutamiento, encuentra el diámetro de una red, indica qué nodos pueden llegar a cuáles y, con una casilla negativa en la diagonal, revela un ciclo negativo.

Explóralo

Abre la aplicación y pulsa Paso. El grafo está a un lado y la tabla al otro. Cada ronda resalta la fila y la columna de la escala actual; cada paso escribe la distancia más corta de un par y rodea las dos casillas que se sumaron. Las casillas que cambiaron en esta ronda están coloreadas. Elige un origen y un destino para ver el camino más corto entre ellos cuando la tabla esté completa.

Preguntas frecuentes

¿Cuál es la complejidad temporal de Floyd–Warshall?

O(n³) para n nodos, sea cual sea el número de aristas, y O(n²) de memoria para la tabla. Es el método preferido para grafos pequeños o densos, donde su bucle simple va muy rápido.

¿Floyd–Warshall o Dijkstra desde cada nodo?

Para un grafo denso, o cuando las aristas pueden ser negativas, Floyd–Warshall es más simple y casi igual de rápido. Para un grafo grande y disperso con aristas no negativas, ejecutar el algoritmo de Dijkstra desde cada nodo es más rápido.

¿Floyd–Warshall es programación dinámica?

Sí. Resuelve el problema para caminos con escalas entre los k primeros nodos usando las respuestas para los k − 1 primeros, y guarda una sola tabla, que va sobrescribiendo.

¿Qué es el cierre transitivo?

La tabla de qué nodos pueden llegar a cuáles, sin tener en cuenta las distancias. La versión de Warshall del algoritmo la calcula con «o» e «y» en lugar de «min» y «+».

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Prueba Floyd–Warshall