El algoritmo de Floyd-Warshall explicado

Mohammed Islam Hadjoudj

Ingeniero experto en investigación de operaciones

1. Introducción al algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall resuelve el problema de los caminos más cortos entre todos los pares. Dado un grafo dirigido y ponderado, halla la distancia más corta entre cada par de vértices, no solo las distancias desde un punto de partida elegido. Cuando termina, dispones de una matriz de distancias completa: consulta cualquier origen y cualquier destino, y la respuesta ya está ahí.

Esta es una pregunta distinta de la que responden el algoritmo de Dijkstra y el de Bellman-Ford. Aquellos son algoritmos de fuente única: les das un vértice de partida y te dicen a qué distancia está cada uno de los demás. Floyd-Warshall responde todas esas preguntas a la vez, para cada posible vértice de partida, en una sola ejecución.

Lo notable del algoritmo es lo poco que necesita para lograrlo. No hay cola de prioridad, ni conjunto de visitados, ni recursión. Todo el algoritmo son tres bucles anidados sobre una matriz, y su corrección descansa sobre una única idea clara tomada de la programación dinámica. Además admite pesos de arista negativos, algo que Dijkstra no puede, e informa de la presencia de un ciclo negativo como efecto secundario del trabajo que ya estaba haciendo.

2. Todos los pares frente a fuente única: ¿por qué no repetir Dijkstra?

Una objeción evidente es que podrías simplemente ejecutar un algoritmo de fuente única una vez desde cada vértice. Ese enfoque es legítimo y a veces preferible, así que conviene precisar cuándo gana cada uno.

Ejecutar el algoritmo de Dijkstra desde los V vértices, con un montículo binario, cuesta O(V * E log V). En un grafo disperso, donde el número de aristas E se acerca a V, eso es aproximadamente O(V2 log V), que supera cómodamente a Floyd-Warshall. En un grafo denso, donde E se aproxima a V2, esa misma repetición cuesta cerca de O(V3 log V), y la cota constante O(V3) de Floyd-Warshall resulta mejor.

Dos consideraciones adicionales suelen zanjar la elección antes que la complejidad:

• Pesos negativos. Repetir Dijkstra es sencillamente incorrecto cuando alguna arista es negativa. Tendrías que sustituirlo por Bellman-Ford, con un coste total de O(V2 * E), o reponderar antes el grafo con el algoritmo de Johnson. Floyd-Warshall acepta aristas negativas directamente.
• Sencillez. Floyd-Warshall son unas cinco líneas de código sin estructuras de datos auxiliares. En los grafos pequeños y densos habituales en planificación, tablas de enrutamiento y programación competitiva, esa fiabilidad vale más que una ventaja asintótica.

3. La idea central: vértices intermedios

La intuición detrás de Floyd-Warshall consiste en restringir el problema de un modo que facilite hacerlo crecer. En lugar de preguntar de entrada "¿cuál es el camino más corto de i a j?", plantea una pregunta más estrecha:

¿Cuál es el camino más corto de i a j que solo puede pasar, como escalas intermedias, por los vértices de cierto conjunto permitido?

Numera los vértices de 1 a V. Define el conjunto permitido como los primeros k vértices y escribe dk(i, j) para la distancia más corta de i a j usando solo {1, 2, ..., k} como vértices intermedios. Los extremos i y j siempre están permitidos, caigan o no dentro del conjunto permitido. Solo están restringidos los vértices estrictamente intermedios.

Los dos extremos de esta definición son reveladores. Cuando k = 0 nada puede servir de escala, así que d0(i, j) es justamente el peso de la arista directa de i a j, o infinito si no existe tal arista. Cuando k = V todos los vértices están permitidos, así que dV(i, j) es la verdadera distancia más corta sin restricciones. El algoritmo es la maquinaria que lleva de la primera a la segunda.

4. La relación de recurrencia

Supón que ya conoces todos los valores de dk-1 y quieres dk. Considera el camino más corto de i a j que puede usar {1, ..., k}. Hay exactamente dos posibilidades, y son mutuamente excluyentes:

1. El camino no usa el vértice k. Entonces solo usa {1, ..., k-1}, así que su longitud es dk-1(i, j), un valor que ya tienes.
2. El camino sí usa el vértice k. Como un camino más corto nunca repite un vértice, pasa por k exactamente una vez. Eso lo divide en un tramo de i a k y otro de k a j, y ninguno de los dos puede usar k como escala. Su longitud es entonces dk-1(i, k) + dk-1(k, j), y ambos términos también son ya conocidos.

El camino más corto es el menor de los dos, lo que da la recurrencia que está en el corazón del algoritmo:

d[k][i][j] = min( d[k-1][i][j],
                  d[k-1][i][k] + d[k-1][k][j] )

En palabras: pasar por k merece la pena solo si el rodeo hasta k y de ahí a j es más corto que la mejor ruta hallada sin él. Esto es programación dinámica en estado puro. Cada subproblema se resuelve una vez, se almacena y se reutiliza.

En la práctica nadie almacena V matrices separadas. Los valores pueden actualizarse in situ en una única matriz V x V, porque durante la iteración k las entradas d(i, k) y d(k, j) no pueden cambiar: actualizar cualquiera de ellas exigiría d(k, k), que vale 0 mientras el grafo no tenga un ciclo negativo. Leer un valor ya sobrescrito en esa misma ronda es por tanto inofensivo, y el consumo de memoria baja de O(V3) a O(V2).

5. Ejecución paso a paso

Las recurrencias abstractas se aclaran en cuanto se ejecutan con números. Tomemos un grafo dirigido de cuatro vértices con estas aristas:

• 1 -> 2 con peso 5
• 1 -> 4 con peso 10
• 2 -> 3 con peso 3
• 3 -> 4 con peso 1

Inicializa la matriz solo a partir de las aristas. La diagonal es 0, porque cada vértice se alcanza a sí mismo sin coste, y toda arista ausente es infinito.

k = 0 (solo aristas directas)

        1     2     3     4
  1     0     5     inf   10
  2     inf   0     3     inf
  3     inf   inf   0     1
  4     inf   inf   inf   0

Ronda k = 1. El vértice 1 queda ahora permitido como escala. Cualquier actualización necesitaría un d(i, 1) finito, pero la columna 1 es infinita en todas partes salvo en la diagonal, porque ninguna arista llega al vértice 1. Nada cambia.

Ronda k = 2. El vértice 2 pasa a estar disponible. La fila 2 ofrece un d(2, 3) = 3 finito, y la columna 2 ofrece un d(1, 2) = 5 finito. De ahí sale una mejora candidata:

• d(1, 3) era infinito. A través del vértice 2 pasa a ser 5 + 3 = 8. Actualizado a 8.

Ronda k = 3. El vértice 3 pasa a estar disponible, y d(3, 4) = 1. Mejoran dos entradas:

• d(1, 4) era 10 por la arista directa. A través del vértice 3 pasa a ser d(1, 3) + d(3, 4) = 8 + 1 = 9. Actualizado a 9.
• d(2, 4) era infinito. A través del vértice 3 pasa a ser 3 + 1 = 4. Actualizado a 4.

Fíjate en que la mejora de d(1, 4) se apoyó en d(1, 3) = 8, un valor descubierto en la ronda anterior. El algoritmo construye caminos largos a partir de caminos cortos que ya ha demostrado.

Ronda k = 4. El vértice 4 no tiene aristas salientes, así que la fila 4 es infinita salvo en la diagonal y ningún camino puede pasar útilmente por él. Nada cambia, y el algoritmo termina.

Resultado (todos los pares)

        1     2     3     4
  1     0     5     8     9
  2     inf   0     3     4
  3     inf   inf   0     1
  4     inf   inf   inf   0

La respuesta para 1 -> 4 es 9, por la ruta 1 -> 2 -> 3 -> 4 con un coste de 5 + 3 + 1, que supera a la arista directa de peso 10. Los infinitos restantes son correctos, no inacabados: ninguna arista entra al vértice 1, así que nada puede alcanzarlo.

6. Implementación y pseudocódigo

El algoritmo es lo bastante breve como para memorizarlo. El detalle que más importa, por encima de cualquier otro, es el orden de los bucles.

function FloydWarshall(W, V):
    // W[i][j] = peso de la arista i -> j, o Infinity si no existe
    // dist es una matriz V x V

    for i from 1 to V:
        for j from 1 to V:
            dist[i][j] = W[i][j]
        dist[i][i] = 0

    // k DEBE ser el bucle más externo
    for k from 1 to V:
        for i from 1 to V:
            for j from 1 to V:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

k debe ser el bucle más externo. Esta es, con diferencia, la forma más común de escribir mal el algoritmo. La recurrencia exige que todo par (i, j) se actualice respecto al vértice intermedio k antes de pasar a k + 1. Si k se coloca en un bucle interno, la matriz se rellena en un orden que carece de significado, y el resultado son distancias que parecen plausibles pero no son óptimas.

Una advertencia de implementación: si representas el infinito con un valor centinela grande como INT_MAX en lugar de un infinito real en coma flotante, dist[i][k] + dist[k][j] puede desbordarse y dar la vuelta hasta un número negativo, que la comparación aceptará encantada. Usa un infinito de verdad o protege la suma omitiendo la actualización cuando alguno de los operandos sea el centinela.

7. Complejidad temporal y espacial

• Tiempo: O(V3). Tres bucles anidados que corren V veces cada uno, con un cuerpo formado por una sola comparación y una asignación. No hay mejor ni peor caso que merezca distinguirse: el algoritmo realiza exactamente V3 pruebas de relajación con cualquier entrada, sin importar cuántas aristas tenga en realidad el grafo.
• Espacio: O(V2). Una matriz de distancias, actualizada in situ. Hace falta una segunda matriz del mismo tamaño si además quieres reconstruir los caminos.

La insensibilidad a E es el rasgo que lo define. Un grafo con cuatro vértices y tres aristas cuesta lo mismo que uno con cuatro vértices y doce. Eso resulta derrochador en grafos dispersos y perfectamente eficiente en los densos. A cambio, la constante es muy pequeña y el patrón de acceso a memoria es regular y aprovecha bien la caché, de modo que Floyd-Warshall suele rendir mejor de lo que sugiere su asintótica en grafos de unos pocos cientos de vértices.

8. Aristas negativas y detección de ciclos negativos

Floyd-Warshall acepta pesos de arista negativos sin modificación alguna. Su recurrencia nunca supone que alargar un camino incremente su longitud, y esa suposición es precisamente la que hace fallar al algoritmo de Dijkstra con entradas negativas.

Los ciclos negativos son otra cuestión, y ningún algoritmo puede devolver distancias mínimas con sentido en su presencia: puedes dar vueltas al ciclo indefinidamente y hundir el coste sin límite. Lo que Floyd-Warshall te ofrece es una forma de advertirlo gratis. Inspecciona la diagonal cuando el algoritmo termine:

for i from 1 to V:
    if dist[i][i] < 0:
        informar "ciclo negativo detectado"

La diagonal se inicializó a 0. Un vértice solo puede acabar con una distancia negativa a sí mismo si existe un recorrido cerrado que empieza y termina en él cuyo peso total está por debajo de cero, que es exactamente la definición de ciclo negativo. Donde Bellman-Ford necesita una pasada adicional específica sobre todas las aristas para determinar lo mismo, a Floyd-Warshall le basta con echar un vistazo a V entradas que ya ha calculado.

Ten en cuenta el alcance de la comprobación. Señala cualquier ciclo negativo en el que participe el vértice correspondiente. Si la diagonal está limpia, toda distancia de la matriz es fiable. Si no lo está, los valores finitos del resto de la matriz deben tratarse como carentes de sentido, no como meramente imprecisos.

9. Reconstruir los caminos reales

La matriz de distancias registra a qué distancia están dos vértices, pero no qué ruta lo consigue. Recuperar la ruta exige una matriz adicional, y el esquema más barato guarda, para cada par, el siguiente vértice del camino.

Inicializa next[i][j] = j siempre que exista una arista directa, y déjalo nulo en caso contrario. Después, cada vez que el bucle principal mejore dist[i][j] pasando por k, hereda el primer paso de la nueva ruta:

if dist[i][k] + dist[k][j] < dist[i][j]:
    dist[i][j] = dist[i][k] + dist[k][j]
    next[i][j] = next[i][k]

La asignación es next[i][k], no k. El primer movimiento del trayecto mejorado de i a j es el primer movimiento del trayecto de i a k, que bien puede ser un vértice completamente distinto. Leer el camino es entonces un paseo corto: empieza en i, sigue next repetidamente y detente al llegar a j. Esto cuesta O(V2) de espacio adicional y ningún tiempo apreciable.

10. Variantes y aplicaciones reales

La estructura de tres bucles se generaliza mucho más allá de los caminos mínimos, porque la recurrencia solo necesita una operación que combine dos tramos y otra que elija entre alternativas.

Clausura transitiva (algoritmo de Warshall)

Sustituye la suma por el Y lógico y el mínimo por el O lógico, y los mismos bucles calculan la alcanzabilidad: si existe o no un camino entre cada par, al margen del coste. Este es el resultado original de Warshall de 1962, y es la razón de que el algoritmo combinado lleve ambos nombres. Aparece en el análisis de flujo de datos de los compiladores, en la resolución de dependencias y en la planificación de consultas de bases de datos.

Camino más ancho y problemas de cuello de botella

Sustituye la suma por el mínimo y el mínimo por el máximo, y el algoritmo halla la ruta cuyo enlace más estrecho es lo más ancho posible. Es la formulación natural para el enrutamiento de máximo ancho de banda en una red y para la planificación de capacidad en logística.

Enrutamiento de redes y matrices de latencia

Los operadores de red necesitan a menudo una matriz completa de latencias o de saltos entre todos los pares de nodos de una topología. Las topologías troncales suelen ser densas y de un número moderado de vértices, que es justo el régimen para el que se creó Floyd-Warshall.

Arbitraje de divisas

Modela las divisas como vértices y los tipos de cambio como aristas. Tomar el logaritmo negativo de cada tipo convierte la multiplicación de tipos en suma de pesos, y un bucle de arbitraje rentable se convierte en un ciclo negativo. La comprobación de la diagonal informa entonces de si existe una oportunidad de arbitraje, y la matriz next reconstruye la secuencia de operaciones.

11. Recursos académicos e historia

La atribución del algoritmo es inusualmente enrevesada. Varios investigadores llegaron a los mismos tres bucles de forma independiente en pocos años.

• Stephen Kleene (1956) describió el procedimiento subyacente al convertir autómatas finitos en expresiones regulares, que estructuralmente es el mismo cálculo de clausura.
• Bernard Roy (1959) publicó el algoritmo en una forma esencialmente moderna en Transitivite et connexite, tres años antes de los artículos que le dieron su nombre habitual.
• Stephen Warshall (1962) publicó la versión de clausura transitiva y demostró el teorema sobre matrices booleanas que lleva su nombre.
• Robert W. Floyd (1962) publicó la versión de caminos mínimos como una nota notablemente breve, Algorithm 97: Shortest Path, en Communications of the ACM.
• Peter Ingerman (1962) describió la formulación hoy estándar de tres bucles anidados en la misma revista ese mismo año.

Para un tratamiento riguroso con demostraciones completas de corrección, la referencia estándar es Cormen, Leiserson, Rivest y Stein, Introduction to Algorithms, en el capítulo sobre caminos mínimos entre todos los pares. Quien compare enfoques para grafos dispersos debería estudiar además el algoritmo de Johnson, que repondera un grafo de modo que repetir Dijkstra siga siendo válido incluso con aristas negativas. Las citas completas figuran al final de este artículo.