Overview
Floyd-Warshall calcula los caminos más cortos entre todos los pares de vértices en un grafo ponderado.
Analogy
Como calcular los precios de vuelo entre todas las ciudades: probar si hace escala en cada ciudad intermedia da un precio más barato.
Step-by-step
- Inicializa dist[i][j] con pesos directos, 0 en diagonal, ∞ si no hay arista
- Para cada vértice intermedio k:
- Para cada par (i,j): dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
- Después de V iteraciones, dist[i][j] es el camino más corto
Visual
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
Common mistakes
- Poner el bucle k dentro en lugar de afuera → resultados incorrectos
- Olvidar que dist[i][i] < 0 indica ciclo negativo
Practice questions
- Encuentra todos los pares de caminos más cortos en un grafo pequeño
- Detecta ciclos negativos comprobando la diagonal
Time
O(V³) — tres bucles anidados sobre vértices
Space
O(V²) — para la matriz de distancias