Floyd-Warshall
Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué problema resuelve
Floyd-Warshall calcula la distancia mínima entre cada par de vértices de un grafo ponderado. Puede usar pesos negativos, pero para interpretar todas las respuestas como distancias finitas no debe haber ciclos negativos.
Conviene cuando necesitas muchas parejas y el grafo es pequeño. El costo es O(n³) tiempo y O(n²) memoria: con 500 vértices son unos 125 millones de combinaciones, así que debes comprobar el límite de tiempo. Para un solo origen, compara con Dijkstra o Bellman-Ford.
Preparar la matriz importa
Crea una matriz d de n × n con INF = 10^18. Pon d[i][i]=0: quedarse en el mismo vértice cuesta cero. Para cada arista u → v de peso w, asigna d[u][v] = min(d[u][v], w); así conservas la mejor entre aristas paralelas. En un grafo no dirigido, actualiza también el sentido inverso.
No escribas cero donde no hay arista: cero es un costo real. Tampoco sobrescribas después con cero una diagonal negativa aportada por un lazo; ese lazo es un ciclo negativo.
La idea: permitir un vértice intermedio nuevo
Al comenzar la pasada de k, conocemos los mejores caminos cuyos vértices intermedios pertenecen a 0,…,k-1. Los extremos i y j pueden ser cualquiera.
Al permitir también k, un camino óptimo puede:
- no pasar por
k: conservad[i][j]; - pasar por
k: une un camino deiakcon otro dekaj.
De ahí sale d[i][j] = min(d[i][j], d[i][k] + d[k][j]). Sin ciclos negativos podemos elegir un camino mínimo sin repetir vértices, así que basta considerar una aparición de k.
Por ejemplo, con 0 → 1 de peso 4, 1 → 2 de peso −2 y 0 → 2 de peso 7:
| Estado | d[0][2] |
|---|---|
| Solo aristas directas | 7 |
| Después de permitir 0 | 7 |
| Después de permitir 1 | min(7, 4−2) = 2 |
| Después de permitir 2 | 2 |
El bucle de k debe ser el exterior para conservar ese significado de las pasadas. No intercambies libremente los tres bucles.
Implementación recomendada (C++)
// d[i][j] = peso de la arista (INF si no hay), d[i][i] = 0. Tras correr: caminos mínimos.
void floyd(vector<vector<long long>>& d) {
int n = d.size();
const long long INF = 1e18;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++) if (d[i][k] < INF)
for (int j = 0; j < n; j++)
if (d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
}La matriz debe ser cuadrada. El código modifica d directamente. Las comprobaciones < INF evitan usar tramos inexistentes; no sustituyen el análisis numérico. Se requiere que todas las distancias finitas y sumas intermedias queden estrictamente entre -INF e INF, incluso durante la ejecución.
Ciclos negativos y respuestas inexistentes
Después de ejecutar, d[v][v] < 0 indica un ciclo negativo que se puede recorrer desde v y volver a v. Una consulta (i,j) no tiene mínimo finito si puede ir de i a alguno de esos vértices y de ahí a j: repetir el ciclo reduce el costo indefinidamente. La función no marca automáticamente esas parejas como «menos infinito».
Si d[i][j] == INF, no hay camino. Es un caso distinto del ciclo negativo y debes imprimir lo que pida el enunciado.
Para comprobarlo
Agrega un vértice 3 aislado al ejemplo. La distancia 0 → 2 sigue siendo 2; 0 → 3 queda en INF y 3 → 3 es 0. Explica por qué ninguna de esas tres respuestas se puede reemplazar por otra.