Algoritmo de Floyd-Warshall

En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica.

El algoritmo de Warshall

El algoritmo de Warshall es un ejemplo de algoritmo booleano. A partir de una tabla inicial compuesta de 0`s (no hay correspondencia inicial en el grafo) y 1`s (hay una correspondencia, llamase “flecha”, entre nodos), obtiene una nueva matriz denominada “Matriz de Clausura Transitiva” en la que se muestran todas las posibles uniones entre nodos, directa o indirectamente. Es decir, si de “A” a “B” no hay una “flecha”, es posible que si haya de “A” a “C” y luego de “C” a “B”. Luego, este resultado se verá volcado en la matriz final.

El algoritmo de Floyd

El algoritmo de Floyd es muy similar, pero trabaja con grafos ponderados. Es decir, el valor de la “flecha” que representamos en la matriz puede ser cualquier número real o infinito. Infinito marca que no existe unión entre los nodos. Esta vez, el resultado será una matriz donde estarán representadas las distancias mínimas entre nodos, seleccionando los caminos más convenientes según su ponderación (“peso”). Por ejemplo, si de “A” a “B” hay 36 (km), pero de “A” a “C” hay 2(km) y de “C” a “B” hay 10 (km), el algoritmo nos devolverá finalmente que de “A” a “B” hay 12 (km).

Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes:

* Formar las matrices iniciales C y D, donde C es la matriz de adyacencia, y D es una matriz del mismo tamaño cargada con valores iniciales Dij = i.

* Se toma k=1.

* Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i≠k, j≠k e i≠j, hacemos:

Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj

En caso contrario, dejamos las matrices como están.

* Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las iteraciones.

* La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino óptimo para ir de un vértice a otro.

Algoritmo

El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo $V^{3}$ comparaciones (esto es notable considerando que puede haber hasta $V^{2}$ aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.

Sea un grafo $G$ con conjunto de vértices $V$ , numerados de 1 a N. Sea además una función ${\textrm {caminoMinimo}}(i,j,k)$ que devuelve el camino mínimo de $i$ a $j$ usando únicamente los vértices de 1 a $k$ como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada $i$ a cada $j$ usando únicamente los vértices de 1 hasta $k+1$ .

Hay dos candidatos para este camino: un camino mínimo, que utiliza únicamente los vértices del conjunto $(1...k)$ ; o bien existe un camino que va desde $i$ hasta $k+1$ , y de $k+1$ hasta $j$ , que es mejor. Sabemos que el camino óptimo de $i$ a $j$ que únicamente utiliza los vértices de 1 hasta $k$ está definido por ${\textrm {caminoMinimo}}(i,j,k)$ , y está claro que si hubiera un camino mejor de $i$ a $k+1$ a $j$ , la longitud de este camino sería la concatenación del camino mínimo de $i$ a $k+1$ (utilizando vértices de $(1...k)$ ) y el camino mínimo de $k+1$ a $j$ (que también utiliza los vértices en $(1...k)$ ).

Por lo tanto, podemos definir $caminoMinimo(i,j,k)$ de forma recursiva:

${\textrm {caminoMinimo}}(i,j,k)=\min({\textrm {caminoMinimo}}(i,j,k-1),{\textrm {caminoMinimo}}(i,k,k-1)\,+\,{\textrm {caminoMinimo}}(k,j,k-1));\,\!$

${\textrm {caminoMinimo}}(i,j,0)={\textrm {pesoArista}}(i,j);\,\!$

Esta fórmula es la base del algoritmo Floyd-Warshall. Funciona ejecutando primero $caminoMinimo(i,j,1)$ para todos los pares $(i,j)$ , usándolos para después hallar $caminoMinimo(i,j,2)$ para todos los pares $(i,j)$ ... Este proceso continúa hasta que $k=n$ , y habremos encontrado el camino más corto para todos los pares de vértices $(i,j)$ usando algún vértice intermedio.

Pseudocodigo

Convenientemente, cuando calculamos el k-esimo caso, se puede sobreescribir la información salvada en la computación k -1. Esto significa que el algoritmo usa memoria cuadrática. Hay que cuidar la inicialización de las condiciones:

1 /* Suponemos que la función pesoArista devuelve el coste del camino que va de i a j
2    (infinito si no existe).
3 También suponemos que  $n$  es el número de vértices y pesoArista(i,i) = 0
4 */
5
6 int camino[][];
7 /* Una matriz bidimensional. En cada paso del algoritmo, camino[i][j] es el camino mínimo 
8 de i hasta j usando valores intermedios de (1..k-1). Cada camino[i][j] es inicializado a 
9
10 */
11
12 procedimiento FloydWarshall ()
13    para k: = 0 hasta n − 1
14
15          camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j])
16
17    fin para

Código en C++

// Declaraciones en el archivo .h
int cn; //cantidad de nodos
vector< vector<int> > ady;

// Devuelve una matriz con las distancias mínimas de cada nodo al resto de los vértices.
vector< vector<int> > Grafo :: floydWarshall(){
    vector< vector<int> > path = this->ady;


    /* No tendría porqué ser necesario si ya hay ceros en las diagonales de ady */
    for(int i = 0; i < cn; i++)
        path[i][i] = 0;
    
    for(int k = 0; k < cn; k++)
        for(int i = 0; i < cn; i++)
            for(int j = 0; j < cn; j++){
                int dt = path[i][k] + path[k][j];
                if(path[i][j] > dt)
                    path[i][j] = dt;
            }
    
    return path;
}

Código en Java

/** Numero de nodos del grafo */
	private int numNodos;
/** Matriz de adyacencia, para almacenar los arcos del grafo */
	private int[][] arcos = new int[TAM][TAM];
/** Matriz de Camino (Warshall - Path) */
	private boolean[][] warshallC = new boolean[TAM][TAM];
	
public void warshall() {
		int i, j, k;

		// Obtener la matriz de adyacencia en P
		for (i = 0; i < numNodos; i++)
			for (j = 0; j < numNodos; j++)
				warshallC[i][j] = (arcos[i][j] != INFINITO);

		// Iterar
		for (k = 0; k < numNodos; k++)
			for (i = 0; i < numNodos; i++)
				for (j = 0; j < numNodos; j++)
					warshallC[i][j] = (warshallC[i][j] || (warshallC[i][k] && warshallC[k][j]));
	}

Comportamiento con ciclos negativos

Para que haya coherencia numérica, Floyd-Warshall supone que no hay ciclos negativos (de hecho, entre cualquier pareja de vértices que forme parte de un ciclo negativo, el camino mínimo no está bien definido porque el camino puede ser infinitamente pequeño). No obstante, si hay ciclos negativos, Floyd-Warshall puede ser usado para detectarlos. Si ejecutamos el algoritmo una vez más, algunos caminos pueden decrementarse pero no garantiza que, entre todos los vértices, caminos entre los cuales puedan ser infinitamente pequeños, el camino se reduzca. Si los números de la diagonal de la matriz de caminos son negativos, es condición necesaria y suficiente para que este vértice pertenezca a un ciclo negativo.

Ejemplo

Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias:

D={\begin{bmatrix}0&3&5&1&\infty &\infty \\3&0&\infty &\infty &9&\infty \\5&\infty &0&7&7&1\\1&\infty &7&0&\infty &4\\\infty &9&7&\infty &0&\infty \\\infty &\infty &1&4&\infty &0\end{bmatrix}}

Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.

1ª Iteración: nodo intermedio = 1

La matriz es simétrica, por lo que solamente hará falta calcular el triángulo superior de las distancias.

d₂₃ = min(d₂₃, d₂₁ + d₁₃) = 8

d₂₄ = min(d₂₄, d₂₁ + d₁₄) = 4

d₂₅ = min(d₂₅, d₂₁ + d₁₅) = 9

d₂₆ = min(d₂₆, d₂₁ + d₁₆) = $\infty$

d₃₂ = min(d₃₂, d₃₁ + d₁₂) = 8

d₃₄ = min(d₃₄, d₃₁ + d₁₄) = 6

d₃₅ = min(d₃₅, d₃₁ + d₁₅) = 7

d₃₆ = min(d₃₆, d₃₁ + d₁₆) = 1

d₄₅ = min(d₄₅, d₄₁ + d₁₅) = $\infty$

d₄₆ = min(d₄₆, d₄₁ + d₁₆) = 4

d₅₆ = min(d₅₆, d₅₁ + d₁₆) = $\infty$

La matriz de distancia después de esta iteración es:

{\mathcal {W}}_{1}={\begin{bmatrix}0&3&5&1&\infty &\infty \\3&0&8&4&9&\infty \\5&8&0&6&7&1\\1&4&6&0&\infty &4\\\infty &9&7&\infty &0&\infty \\\infty &\infty &1&4&\infty &0\end{bmatrix}}

2ª Iteración: nodo intermedio = 2

d₁₃ = min(d₁₃, d₁₂ + d₂₃) = 5

d₁₄ = min(d₁₄, d₁₂ + d₂₄) = 1

d₁₅ = min(d₁₅, d₁₂ + d₂₅) = 12

d₁₆ = min(d₁₆, d₁₂ + d₂₆) = $\infty$

d₃₄ = min(d₃₄, d₃₂ + d₂₄) = 6

d₃₅ = min(d₃₅, d₃₂ + d₂₅) = 7

d₃₆ = min(d₃₆, d₃₂ + d₂₆) = 1

d₄₅ = min(d₄₅, d₄₂ + d₂₅) = 13

d₄₆ = min(d₄₆, d₄₂ + d₂₆) = 4

d₅₆ = min(d₅₆, d₅₂ + d₂₆) = $\infty$

La matriz de distancia después de esta iteración es:

{\mathcal {W}}_{2}={\begin{bmatrix}0&3&5&1&12&\infty \\3&0&8&4&9&\infty \\5&8&0&6&7&1\\1&4&6&0&13&4\\12&9&7&13&0&\infty \\\infty &\infty &1&4&\infty &0\end{bmatrix}}

3ª Iteración: nodo intermedio = 3

d₁₂ = min(d₁₂, d₁₃ + d₃₂) = 3

d₁₄ = min(d₁₄, d₁₃ + d₃₄) = 1

d₁₅ = min(d₁₅, d₁₃ + d₃₅) = 12

d₁₆ = min(d₁₆, d₁₃ + d₃₆) = 6

d₂₄ = min(d₂₄, d₂₃ + d₃₄) = 4

d₂₅ = min(d₂₅, d₂₃ + d₃₅) = 9

d₂₆ = min(d₂₆, d₂₃ + d₃₆) = 9

d₄₅ = min(d₄₅, d₄₃ + d₃₅) = 13

d₄₆ = min(d₄₆, d₄₃ + d₃₆) = 4

d₅₆ = min(d₅₆, d₅₃ + d₃₆) = 8

La matriz de distancia después de esta iteración es:

{\mathcal {W}}_{3}={\begin{bmatrix}0&3&5&1&12&6\\3&0&8&4&9&9\\5&8&0&6&7&1\\1&4&6&0&13&4\\12&9&7&13&0&8\\6&9&1&4&8&0\end{bmatrix}}

4ª Iteración: nodo intermedio = 4

d₁₂ = min(d₁₂, d₁₄ + d₄₂) = 3

d₁₃ = min(d₁₃, d₁₄ + d₄₃) = 5

d₁₅ = min(d₁₅, d₁₄ + d₄₅) = 12

d₁₆ = min(d₁₆, d₁₄ + d₄₆) = 5

d₂₃ = min(d₂₃, d₂₄ + d₄₃) = 8

d₂₅ = min(d₂₅, d₂₄ + d₄₅) = 9

d₂₆ = min(d₂₆, d₂₄ + d₄₆) = 8

d₃₅ = min(d₃₅, d₃₄ + d₄₅) = 7

d₃₆ = min(d₃₆, d₃₄ + d₄₆) = 1

d₅₆ = min(d₅₆, d₅₄ + d₄₆) = 8

La matriz de distancia después de esta iteración es:

{\mathcal {W}}_{4}={\begin{bmatrix}0&3&5&1&12&5\\3&0&8&4&9&8\\5&8&0&6&7&1\\1&4&6&0&13&4\\12&9&7&13&0&8\\5&8&1&4&8&0\end{bmatrix}}

5ª Iteración: nodo intermedio = 5

d₁₂ = min(d₁₂, d₁₅ + d₅₂) = 3

d₁₃ = min(d₁₃, d₁₅ + d₅₃) = 5

d₁₄ = min(d₁₄, d₁₅ + d₅₄) = 1

d₁₆ = min(d₁₆, d₁₅ + d₅₆) = 5

d₂₃ = min(d₂₃, d₂₅ + d₅₃) = 8

d₂₄ = min(d₂₄, d₂₅ + d₅₄) = 4

d₂₆ = min(d₂₆, d₂₅ + d₅₆) = 8

d₃₄ = min(d₃₄, d₃₅ + d₅₄) = 6

d₃₆ = min(d₃₆, d₃₅ + d₅₆) = 1

d₄₆ = min(d₄₆, d₄₅ + d₅₆) = 4

La matriz de distancia después de esta iteración es:

{\mathcal {W}}_{5}={\mathcal {W}}_{4}={\begin{bmatrix}0&3&5&1&12&5\\3&0&8&4&9&8\\5&8&0&6&7&1\\1&4&6&0&13&4\\12&9&7&13&0&8\\5&8&1&4&8&0\end{bmatrix}}

6ª Iteración: nodo intermedio = 6

d₁₂ = min(d₁₂, d₁₆ + d₆₂) = 3

d₁₃ = min(d₁₃, d₁₆ + d₆₃) = 5

d₁₄ = min(d₁₄, d₁₆ + d₆₄) = 1

d₁₅ = min(d₁₅, d₁₆ + d₆₅) = 12

d₂₃ = min(d₂₃, d₂₆ + d₆₃) = 8

d₂₄ = min(d₂₄, d₂₆ + d₆₄) = 4

d₂₅ = min(d₂₅, d₂₆ + d₆₅) = 9

d₃₄ = min(d₃₄, d₃₆ + d₆₄) = 5

d₃₅ = min(d₃₅, d₃₆ + d₆₅) = 7

d₄₅ = min(d₄₅, d₄₆ + d₆₅) = 12

La matriz de distancia después de esta iteración es:

{\mathcal {W}}_{6}={\begin{bmatrix}0&3&5&1&12&5\\3&0&8&4&9&8\\5&8&0&5&7&1\\1&4&5&0&12&4\\12&9&7&12&0&8\\5&8&1&4&8&0\end{bmatrix}}

Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mínimo entre 2 vértices cualesquiera del grafo será el obtenido en la matriz final. En este caso, el camino mínimo entre 3 y 4 vale 5.

Análisis

Si utilizamos matrices booleanas, para encontrar todos los ${\mathit {n}}^{2}$ de ${\mathcal {W}}_{k}$ desde ${\mathcal {W}}_{{\mathit {k}}-1}$ se necesita hacer $2{\mathit {n}}^{2}$ operaciones binarias. Debido a que empezamos con ${\mathcal {W}}_{0}={\mathcal {W}}_{\mathcal {R}}$ y computamos la secuencia de ${\mathit {n}}$ matrices booleanas ${\mathcal {W}}_{1}$ , ${\mathcal {W}}_{2}$ , $...$ , ${\mathcal {W}}_{\mathit {n}}={\mathcal {M}}_{{\mathcal {R}}^{*}}$ , el número total de operaciones binarias es de ${\mathit {n}}\times 2{\mathit {n}}^{2}=2{\mathit {n}}^{3}$ . Por lo tanto, la complejidad del algoritmo es $\Theta ({n}^{3})$ y puede ser resuelto por una máquina determinista de Turing en tiempo polinómico.

Aplicaciones y generalizaciones

El algoritmo de Floyd-Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:

Camino mínimo en grafos dirigidos (algoritmo de Floyd).
Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El grafo es un grafo no ponderado y representado por una matriz booleana de adyacencia. Entonces la operación de adición es reemplazada por la conjunción lógica(AND) y la operación menor por la disyunción lógica (OR).
Encontrar una expresión regular dada por un lenguaje regular aceptado por un autómata finito (algoritmo de Kleene).
Inversión de matrices de números reales (algoritmo de Gauss-Jordan).
Ruta óptima. En esta aplicación es interesante encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar los mínimos con el pseudocodigo anterior, se coge el máximo. Los pesos de las aristas representan las limitaciones del flujo. Los pesos de los caminos representan cuellos de botella; por ello, la operación de adición anterior es reemplazada por la operación mínimo.
Comprobar si un grafo no dirigido es bipartito.

Implementación del algoritmo de Floyd-Warshall

Implementación en C - joshuarobinson.net Archivado el 7 de septiembre de 2011 en Wayback Machine. (en inglés). (Este enlace ya no es válido)
Implementación en PHP - julmis.julmajanne.com Archivado el 29 de septiembre de 2011 en Wayback Machine. (gracias a Janne Mikkonen).
Implementación en Java (explicación paso a paso) - explicación y applet disponible en pms.ifi.lmu.de (en inglés)

Referencias

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1º Edición edición). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
- Sección 26.2, "The Floyd–Warshall algorithm", pág. 558–565;
- Sección 26.4, "A general framework for solving path problems in directed graphs", pág. 570–576.
Floyd, Robert W. (junio de 1962). «Algorithm 97: Shortest Path». Communications of the ACM 5 (6): 345. doi 10.1145/367766.368168.
Kleene, S. C. (1956). «Representation of events in nerve nets and finite automata». En C. E. Shannon y John McCarthy, ed. Automata Studies. Princeton University Press. pp. 3-42.
Warshall, Stephen (enero de 1962). «A theorem on Boolean matrices». Journal of the ACM 9 (1): 11-12. doi 10.1145/321105.321107.
Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5ª Edición. Addison Wesley. ISBN 0-07-119881-4.

Véase también

Enlaces externos

Video Tutorial en VideoPractico.com de Floyd

Datos: Q1047576
Multimedia: Floyd-Warshall algorithm / Q1047576