Floyd-Warshall: caminos más cortos entre todos los pares

La distancia más corta de cada par, en un solo triple ciclo. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

La idea: permitir intermedios uno a la vez

• Subproblema: el i→j más corto usando solo los nodos {0..k−1} como puntos de paso
• Haz crecer k en uno: o el camino viejo, o i → k → j
• Cuando ya se permitió cada nodo, las distancias son finales
• k DEBE ser el ciclo más externo (o calcula basura en silencio)

Mira cómo se llena la matriz

Celda (i,j) = mejor distancia hasta ahora · oscuro = ∞ · diagonal verde azulado = 0. Cada cuadro enciende un nodo intermedio; las celdas que mejoran destellan en naranja.

El costo es ciego a la densidad

Floyd-Warshall = plano (ignora la cantidad de aristas). Dijkstra×V = sube con las aristas. Disperso: Dijkstra×V 5× más rápido. Denso: la brecha se cierra a 1.4×; compilado → gana FW.

Extras gratis

• Aristas negativas: manejadas (como Bellman-Ford)
• Ciclo negativo: dist[i][i] < 0 en la diagonal
• Cerradura transitiva: mismo ciclo, or/and en lugar de min/plus (Warshall 1962)
• Memoria O(V²) ⇒ solo grafos chicos o densos

Para llevar

Tres líneas, todos los pares. Especialista en chicos/densos; malo para dispersos enormes. Hilo de caminos más cortos completo: BFS · Dijkstra · Bellman-Ford · Floyd-Warshall. Siguiente: A* — una heurística que dirige hacia una meta.