Algoritmo de Floyd-Warshall explicado: cómo funciona, código y complejidad

Qué problema resuelve Floyd-Warshall

A veces necesitas la distancia entre todos los pares de lugares, no solo desde un origen: una tabla de tiempos de viaje entre todas las ciudades, la latencia entre cada par de servidores o la alcanzabilidad completa de un grafo de dependencias. Floyd-Warshall resuelve este problema de caminos más cortos entre todos los pares con un algoritmo de programación dinámica muy breve.

Lo publicó Robert Floyd en 1962 ("Algorithm 97: Shortest path"), a partir del algoritmo de Stephen Warshall, también de 1962, para la clausura transitiva.

La idea en palabras sencillas

Numera los nodos de 0 a V − 1. Tras procesar el nodo k, dist[i][j] es el camino más corto de i a j que usa como paradas intermedias solo los nodos de 0 a k. Permitir un nodo intermedio más, k, da dos opciones: el mejor camino anterior que evita k, o un camino i → k → j formado por dos mejores caminos que ya usan solo nodos anteriores a k.

1. Rellena la matriz: 0 en la diagonal, el peso de la arista donde exista y infinito en el resto.
2. Para k = 0 hasta V − 1, para cada par (i, j): si dist[i][k] + dist[k][j] < dist[i][j], actualízalo.
3. Tras el último k, la matriz contiene todas las distancias mínimas. Un valor negativo en la diagonal indica un ciclo negativo.

El orden de los bucles es esencial: k debe ser el bucle exterior.

Ejemplo resuelto, paso a paso

Grafo dirigido con 4 nodos y las aristas 0→1 (3), 0→3 (7), 1→0 (8), 1→2 (2), 2→0 (5), 2→3 (1), 3→0 (2). Matriz inicial (fila = origen, columna = destino):

1. k = 0: los caminos pueden pasar por el nodo 0. 1→3 pasa a ser 8 + 7 = 15, 2→1 pasa a ser 5 + 3 = 8 y 3→1 pasa a ser 2 + 3 = 5.
2. k = 1: por el nodo 1. 0→2 pasa a ser 3 + 2 = 5 y 3→2 pasa a ser 5 + 2 = 7.
3. k = 2: por el nodo 2. 0→3 mejora de 7 a 5 + 1 = 6, 1→3 de 15 a 2 + 1 = 3 y 1→0 de 8 a 2 + 5 = 7.
4. k = 3: por el nodo 3. 1→0 mejora de 7 a 3 + 2 = 5, 2→0 de 5 a 1 + 2 = 3 y 2→1 de 8 a 1 + 5 = 6.

Filas de la matriz final: 0 → [0, 3, 5, 6], 1 → [5, 0, 2, 3], 2 → [3, 6, 0, 1], 3 → [2, 5, 7, 0].

Implementación en Python

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

La matriz nxt guarda el primer paso del mejor camino de i a j, lo que basta para reconstruir cualquier camino:

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

Si tienes muchos nodos y quieres velocidad en Python, el mismo triple bucle se puede escribir con NumPy como una actualización vectorizada por cada k: d = np.minimum(d, d[:, k, None] + d[None, k, :]).

Complejidad temporal y espacial

En grafos dispersos con pesos no negativos, ejecutar Dijkstra desde cada nodo cuesta O(V × (V + E) log V), que es más rápido que O(V³) cuando E es mucho menor que V².

Variantes y errores comunes

• Ciclos negativos: tras los bucles, si dist[i][i] < 0 para algún i, el nodo i está en un ciclo negativo y los caminos más cortos que pasan por él no están definidos.
• Clausura transitiva (Warshall): usa booleanos y sustituye min/suma por or/and: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).
• Caminos minimax y maximin: sustituye + por max (o min) para encontrar, por ejemplo, el camino cuya arista mayor sea lo más pequeña posible.
• Usa un número finito grande en lugar de infinito solo si estás seguro de que la suma de dos de ellos no puede desbordarse; en Python, float("inf") es la opción segura.
• Inicializa la diagonal a 0 y, cuando haya aristas paralelas, conserva el peso menor.

Cuándo usarlo y usos en el mundo real

• Precalcular una tabla de distancias entre todas las estaciones, almacenes o ciudades para consultas posteriores.
• Análisis de grafos, como la centralidad de cercanía o el diámetro de una red pequeña.
• Problemas de entrevista: encontrar la ciudad con menos vecinos dentro de un umbral de distancia, evaluar divisiones (razones como productos de caminos), prerrequisitos de cursos como clausura transitiva.