Floyd-Warshall resuelve el problema de todos los pares de caminos más cortos (APSP) en O(V³) usando programación dinámica. A diferencia de ejecutar Dijkstra desde cada nodo (O(V(E + V log V))), Floyd-Warshall es independiente del número de aristas y maneja pesos negativos.

Es el algoritmo de referencia para grafos densos o cuando necesitas la matriz completa de distancias. Su simplicidad es elegante: dist[i][j] considera cada nodo k como posible intermedio.

Cómo Funciona

1. Inicializa: dist[i][j] = peso(i,j) si la arista existe, 0 si i=j, ∞ en caso contrario.
2. Recurre: para cada nodo intermedio k de 1 a V:
   • “Para cada par (i, j):” dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. Detecta ciclos: si dist[i][i] < 0 para algún i, hay un ciclo negativo alcanzable.

Idea Clave

La programación dinámica considera nodos intermedios incrementalmente. Después de procesar los primeros k nodos como intermedios, dist[i][j] contiene el camino más corto que solo usa nodos {1..k} como intermedios.

Al añadir el nodo k+1, solo necesitas verificar si pasar por k+1 mejora el camino: dist[i][j] = min(sin_k+1, por_k+1). Esto se hace en O(1) por par, dando O(V³) total.

Ejemplo Trabajado

Grafo 4×4:

    1    2    3    4
1 [ 0,   3,   ∞,   7 ]
2 [ 8,   0,   2,   ∞ ]
3 [ 5,   ∞,   0,   1 ]
4 [ 2,   ∞,   ∞,   0 ]

k=1 (nodo 1 como intermedio):

• dist[2][1] + dist[1][3] = 8+∞ = ∞ → no mejora
• dist[4][1] + dist[1][2] = 2+3 = 5 → mejora dist[4][2] de ∞ a 5
• dist[4][1] + dist[1][3] = 2+∞ = ∞ → no mejora

k=2 (nodo 2 como intermedio):

• dist[1][2] + dist[2][3] = 3+2 = 5 → mejora dist[1][3] de ∞ a 5
• dist[4][2] + dist[2][3] = 5+2 = 7 → mejora dist[4][3] de ∞ a 7

k=3 (nodo 3 como intermedio):

• dist[1][3] + dist[3][4] = 5+1 = 6 → mejora dist[1][4] de 7 a 6
• dist[2][3] + dist[3][4] = 2+1 = 3 → mejora dist[2][4] de ∞ a 3
• dist[4][3] + dist[3][4] = 7+1 = 8 → no mejora dist[4][4]

k=4 (nodo 4 como intermedio):

• Mejoras adicionales si existen

Matriz final (distancias mínimas):

    1    2    3    4
1 [ 0,   3,   5,   6 ]
2 [ 5,   0,   2,   3 ]
3 [ 3,   6,   0,   1 ]
4 [ 2,   5,   7,   0 ]

Observa el visualizador mostrar la matriz dist actualizándose en cada iteración k.

Casos Extremos y Trampas

• Ciclos negativos — dist[i][i] < 0 después del algoritmo. No hay solución APSP bien definida.
• “Grafo disperso — O(V³) es desperdicio si E << V². Mejor: Dijkstra desde cada nodo.”
• Overflow — usa ∞ = Number.MAX_SAFE_INTEGER / 2 para evitar overflow en sumas.
• Reconstrucción de caminos — guarda una matriz next[i][j] para reconstruir el camino real.

Comparación con Dijkstra múltiple

Aplicaciones

• APSP completo — necesitas todos los pares (flota de vehículos, rutas)
• Cierre transitivo — ¿existe camino de i a j? (booleano en lugar de pesos)
• Detección de ciclos negativos — revisa dist[i][i] < 0
• Enseñanza — ejemplo clásico de DP en grafos

Trayectoria de Práctica

1. Implementa Floyd-Warshall en una matriz 4×4; traza cada iteración k.
2. Modifica para detectar ciclos negativos; prueba en un grafo con ciclo de peso -2.
3. Añade matriz next para reconstruir el camino de 1 a 4.
4. Compara con ejecutar Dijkstra 4 veces: ¿cuál es más rápido para V=100, E=200?
5. Investiga Johnson’s algorithm: ¿cómo combina Bellman-Ford + Dijkstra para APSP en grafos dispersos?