Algoritmo de Floyd-Warshall

Dado un grafo ponderado $G$ dirigido o no dirigido con $n$ vértices. La tarea es encontrar la longitud del camino más corto $d_{ij}$ entre cada par de vértices $i$ y $j$ .

El grafo puede tener aristas de peso negativo, pero no ciclos de peso negativo.

Si hay un ciclo negativo, se puede recorrer ese ciclo una y otra vez, y en cada iteración el costo del camino se hace más chico. Así se pueden hacer ciertos caminos arbitrariamente chicos, o en otras palabras el camino más corto está indefinido. Eso automáticamente significa que un grafo no dirigido no puede tener aristas de peso negativo, porque tal arista ya forma un ciclo negativo: se puede ir y volver por esa arista tanto como se quiera.

Este algoritmo también se puede usar para detectar la presencia de ciclos negativos. El grafo tiene un ciclo negativo si al final del algoritmo la distancia de un vértice $v$ a sí mismo es negativa.

Este algoritmo se publicó simultáneamente en artículos de Robert Floyd y Stephen Warshall en 1962. Sin embargo, en 1959 Bernard Roy publicó esencialmente el mismo algoritmo, pero su publicación pasó desapercibida.

Descripción del algoritmo

La idea clave del algoritmo es partir el proceso de encontrar el camino más corto entre cualesquiera dos vértices en varias fases incrementales.

Numérense los vértices de 1 a $n$ . La matriz de distancias es $d[ ][ ]$ .

Antes de la $k$ -ésima fase ( $k = 1 \dots n$ ), $d[i][j]$ para cualesquiera vértices $i$ y $j$ guarda la longitud del camino más corto entre el vértice $i$ y el vértice $j$ que contiene solo los vértices ${1, 2, …, k-1}$ como vértices internos del camino.

En otras palabras, antes de la $k$ -ésima fase el valor de $d[i][j]$ es igual a la longitud del camino más corto del vértice $i$ al vértice $j$ , si a este camino se le permite entrar solo a vértices con números menores que $k$ (el inicio y el fin del camino no están restringidos por esta propiedad).

Es fácil verificar que esta propiedad vale para la primera fase. Para $k = 0$ , podemos llenar la matriz con $d[i][j] = w_{i j}$ si existe una arista entre $i$ y $j$ con peso $w_{i j}$ y $d[i][j] = \infty$ si no existe. En la práctica $\infty$ será algún valor alto. Como veremos más adelante, esto es un requisito del algoritmo.

Supongamos ahora que estamos en la $k$ -ésima fase, y queremos computar la matriz $d[ ][ ]$ de modo que cumpla los requisitos de la fase $(k + 1)$ . Hay que fijar las distancias de algunos pares de vértices $(i, j)$ . Hay dos casos fundamentalmente distintos:

El camino más corto del vértice $i$ al vértice $j$ con vértices internos del conjunto ${1, 2, \dots, k}$ coincide con el camino más corto con vértices internos del conjunto ${1, 2, \dots, k-1}$ .

En este caso, $d[i][j]$ no cambiará durante la transición.
El camino más corto con vértices internos de ${1, 2, \dots, k}$ es más corto.

Esto significa que el camino nuevo, más corto, pasa por el vértice $k$ . Esto significa que podemos partir el camino más corto entre $i$ y $j$ en dos caminos: el camino entre $i$ y $k$ , y el camino entre $k$ y $j$ . Está claro que ambos caminos solo usan vértices internos de ${1, 2, \dots, k-1}$ y son los más cortos en ese sentido. Por lo tanto ya computamos las longitudes de esos caminos antes, y podemos computar la longitud del camino más corto entre $i$ y $j$ como $d[i][k] + d[k][j]$ .

Combinando estos dos casos encontramos que podemos recalcular la longitud de todos los pares $(i, j)$ en la $k$ -ésima fase de la siguiente manera:

$d_{\text{new}}[i][j] = min(d[i][j], d[i][k] + d[k][j])$

Así, todo el trabajo requerido en la $k$ -ésima fase es iterar sobre todos los pares de vértices y recalcular la longitud del camino más corto entre ellos. Como resultado, después de la $n$ -ésima fase, el valor $d[i][j]$ en la matriz de distancias es la longitud del camino más corto entre $i$ y $j$ , o es $\infty$ si el camino entre los vértices $i$ y $j$ no existe.

Una última observación: no necesitamos crear una matriz de distancias separada $d_{\text{new}}[ ][ ]$ para guardar temporalmente los caminos más cortos de la $k$ -ésima fase; es decir, todos los cambios se pueden hacer directamente en la matriz $d[ ][ ]$ en cualquier fase. De hecho, en cualquier $k$ -ésima fase a lo sumo mejoramos la distancia de cualquier camino en la matriz de distancias, por lo tanto no podemos empeorar la longitud del camino más corto de ningún par de vértices que se procesará en la fase $(k+1)$ o posterior.

La complejidad temporal de este algoritmo es obviamente $O(n^3)$ .

Implementación

Sea $d[][]$ un arreglo 2D de tamaño $n \times n$ , llenado según la fase $0$ como se explicó antes. También pondremos $d[i][i] = 0$ para cualquier $i$ en la fase $0$ .

Entonces el algoritmo se implementa así:


for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

Se asume que si no hay arista entre cualesquiera dos vértices $i$ y $j$ , entonces la matriz en $d[i][j]$ contiene un número grande (lo suficientemente grande como para que sea mayor que la longitud de cualquier camino en este grafo). Entonces esta arista siempre será desventajosa de tomar, y el algoritmo funcionará correctamente.

Sin embargo, si hay aristas de peso negativo en el grafo, hay que tomar medidas especiales. Si no, los valores resultantes en la matriz pueden ser de la forma $\infty - 1$ , $\infty - 2$ , etc., que por supuesto siguen indicando que entre los vértices respectivos no existe un camino. Por lo tanto, si el grafo tiene aristas de peso negativo, es mejor escribir el algoritmo de Floyd-Warshall de la siguiente manera, para que no haga transiciones usando caminos que no existen.


for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

Recuperar la secuencia de vértices en el camino más corto

Es fácil mantener información adicional con la cual será posible recuperar el camino más corto entre cualesquiera dos vértices dados en forma de una secuencia de vértices.

Para esto, además de la matriz de distancias $d[ ][ ]$ , hay que mantener una matriz de ancestros $p[ ][ ]$ , que contendrá el número de la fase en la que se modificó por última vez la distancia más corta entre dos vértices. Está claro que el número de la fase no es otra cosa que un vértice en el medio del camino más corto deseado. Ahora solo hay que encontrar el camino más corto entre los vértices $i$ y $p[i][j]$ , y entre $p[i][j]$ y $j$ . Esto lleva a un algoritmo recursivo simple de reconstrucción del camino más corto.

El caso de pesos reales

Si los pesos de las aristas no son enteros sino reales, es necesario tener en cuenta los errores que ocurren al trabajar con tipos float.

El algoritmo de Floyd-Warshall tiene el efecto desagradable de que los errores se acumulan muy rápido. De hecho, si hay un error en la primera fase de $\delta$ , este error puede propagarse a la segunda iteración como $2 \delta$ , a la tercera como $4 \delta$ , y así sucesivamente.

Para evitarlo, el algoritmo se puede modificar para tener en cuenta el error (EPS = $\delta$ ) usando la siguiente comparación:


if (d[i][k] + d[k][j] < d[i][j] - EPS)
    d[i][j] = d[i][k] + d[k][j];

El caso de ciclos negativos

Formalmente el algoritmo de Floyd-Warshall no aplica a grafos que contienen ciclo(s) de peso negativo. Pero para todos los pares de vértices $i$ y $j$ para los cuales no existe un camino que empiece en $i$ , visite un ciclo negativo y termine en $j$ , el algoritmo seguirá funcionando correctamente.

Para el par de vértices para el cual la respuesta no existe (por la presencia de un ciclo negativo en el camino entre ellos), el algoritmo de Floyd guardará cualquier número (quizá muy negativo, pero no necesariamente) en la matriz de distancias. Sin embargo es posible mejorar el algoritmo de Floyd-Warshall para que trate con cuidado esos pares de vértices y los reporte, por ejemplo como $-\text{INF}$ .

Esto se puede hacer de la siguiente manera: corramos el algoritmo de Floyd-Warshall usual para un grafo dado. Entonces un camino más corto entre los vértices $i$ y $j$ no existe si y solo si hay un vértice $t$ tal que $t$ es alcanzable desde $i$ y $j$ es alcanzable desde $t$ , para el cual $d[t][t] < 0$ .

Además, al usar el algoritmo de Floyd-Warshall para grafos con ciclos negativos, hay que tener en cuenta que pueden surgir situaciones en las que las distancias se vuelven negativas de forma exponencialmente rápida. Por lo tanto el desbordamiento entero se debe manejar limitando la distancia mínima por algún valor (p. ej. $-\text{INF}$ ).

Para aprender más sobre encontrar ciclos negativos en un grafo, ver el artículo separado Finding a negative cycle in the graph.