Floyd-Warshall calcula las distancias mínimas entre todos los pares de vértices. Utiliza programación dinámica y una matriz que mejora al incorporar cada nodo como posible intermediario.
Dijkstra y Bellman-Ford resuelven caminos mínimos desde un origen. Cuando necesitamos responder consultas entre muchos pares, repetir un algoritmo puede ser posible, pero existe una alternativa matricial especialmente clara: Floyd-Warshall.
El algoritmo calcula simultáneamente la distancia mínima desde cada vértice hacia todos los demás. Admite pesos negativos, siempre que interpretemos correctamente los efectos de los ciclos negativos.
Dado un grafo dirigido o no dirigido ponderado, Floyd-Warshall produce una matriz D tal que:
Si j no es alcanzable desde i, el valor permanece en infinito. El resultado contiene V² respuestas, una para cada par ordenado.
Antes de comenzar se construye la matriz:
Si existen varias aristas entre el mismo par, se conserva inicialmente la de menor peso.
Los vértices se consideran progresivamente como posibles intermediarios. Para cada k se pregunta si el camino i → k → j mejora el mejor camino conocido de i hasta j.
La fórmula resume dos posibilidades: conservar el camino anterior o utilizar k para unir un camino mínimo de i a k con otro de k a j.
Después de procesar el vértice k, D[i][j] contiene el mejor costo usando únicamente los vértices ya considerados como intermediarios.
Al finalizar la última etapa, todos los vértices pueden actuar como intermediarios y la matriz contiene las distancias mínimas globales.
Avanza un intermediario por vez. Las celdas rosas mejoraron en la última etapa. Puedes agregar C → A con peso 1 para crear el ciclo negativo A → E → D → C → A.
Matriz de distancias
Acción actual
Una celda roja en la diagonal indica una distancia D[i][i] negativa y, por lo tanto, un ciclo negativo alcanzable desde i y capaz de regresar a i.
function floydWarshall(matriz) {
const n = matriz.length;
const distancia = matriz.map(fila => [...fila]);
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (distancia[i][k] !== Infinity &&
distancia[k][j] !== Infinity) {
distancia[i][j] = Math.min(
distancia[i][j],
distancia[i][k] + distancia[k][j]
);
}
}
}
}
return distancia;
}La demostración se apoya en que cada etapa habilita exactamente un nuevo intermediario. Por eso el bucle de k debe envolver a los bucles de i y j.
Intercambiar i y j no altera la idea, pero colocar k dentro puede usar información en un orden que rompe la recurrencia y dejar caminos sin descubrir.
Matemáticamente, infinito más un valor finito continúa siendo infinito. En código es conveniente verificar que ambos tramos existan antes de sumarlos.
Esta comprobación es imprescindible en lenguajes donde el infinito se representa mediante un número centinela que podría desbordarse al sumarlo.
La matriz de distancias informa el costo, pero no la secuencia de vértices. Para reconstruir rutas se mantiene una matriz siguiente.
El valor almacenado indica el primer paso que debemos tomar desde i para avanzar hacia j.
function reconstruirCamino(siguiente, origen, destino) {
if (siguiente[origen][destino] === null) return null;
const camino = [origen];
let actual = origen;
while (actual !== destino) {
actual = siguiente[actual][destino];
camino.push(actual);
}
return camino;
}Si el par está afectado por un ciclo negativo, no debe reconstruirse como si tuviera un camino mínimo finito.
Sin ciclos negativos, la distancia mínima de un vértice hacia sí mismo es 0. Si al terminar aparece un valor negativo en la diagonal, existe un ciclo negativo.
Floyd-Warshall permite detectar ciclos negativos en cualquier componente del grafo, no solo los alcanzables desde un origen particular.
Si D[k][k] es negativo, un par i, j queda afectado cuando i puede llegar a k y k puede llegar a j. En tal caso el camino puede atravesar el ciclo repetidamente y reducir su costo sin límite.
Una implementación completa puede marcar esos pares con -Infinity después de ejecutar las etapas principales.
Warshall calcula alcanzabilidad usando operaciones booleanas. Floyd-Warshall conserva la misma estructura de tres bucles, pero trabaja con costos.
| Algoritmo | Operación | Resultado |
|---|---|---|
| Warshall | OR y AND | Existe o no existe un camino |
| Floyd-Warshall | mínimo y suma | Costo del camino mínimo |
| Algoritmo | Orígenes | Pesos negativos | Tiempo |
|---|---|---|---|
| Dijkstra | Uno | No | O((V + E) log V) |
| Bellman-Ford | Uno | Sí | O(VE) |
| Floyd-Warshall | Todos | Sí | O(V³) |
Para grafos dispersos grandes sin pesos negativos puede ser mejor ejecutar Dijkstra desde cada origen. Floyd-Warshall resulta atractivo para grafos densos, tamaños moderados y consultas entre todos los pares.
Los tres bucles recorren todas las combinaciones de k, i y j. Las matrices de distancia y reconstrucción requieren espacio cuadrático.
Floyd-Warshall condensa el problema de todos los caminos mínimos en una recurrencia compacta. Cada etapa permite un nuevo intermediario hasta convertir la matriz inicial de aristas en una tabla completa de distancias.
En el próximo tema estudiaremos los árboles de expansión mínima, cuyo objetivo no es optimizar rutas individuales, sino conectar todos los vértices con el menor costo total.