Floyd-Warshall

Floyd-Warshall Creador Bernard Roy. Fecha de Creación 1959

Floyd-Warshall. Es un algoritmo de análisis sobre grafos que permite 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, constituyendo un ejemplo de programación dinámica.

Características

• Obtiene la mejor ruta entre todo par de nodos.

• Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos.

• La iteración se produce sobre nodos intermedios, o sea para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red. Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.

• El algoritmo da sólo la menor distancia; se debe manejar información adicional para encontrar tablas de encaminamiento.

• Hasta no hallar la última matriz no se encuentran las distancias mínimas.

• Su complejidad es del orden de N³.

Función

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³ comparaciones, lo hace mejorando 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 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, el 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, después 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 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: CaminoMinimo(i,j,k) = min(CaminoMinimo(i,j,k-1),CaminoMinimo(i,k,k-1)+CaminoMinimo(k,j,k-1)); CaminoMinimo(i,j,0) = 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.

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.

Pseudocódigo y Código en C++

Pseudocódigo del algoritmo Floyd-Warshall

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

Código C++ del algoritmo Floyd-Warshall

  // Declaraciones en el archivo .h
 int cn; //cantidad de nodos
 vector< vector<int> > ady; // [[matriz de adyacencia]]
 // Devuelve una matriz con las distancias mínimas de cada nodo al resto de los vértices.
 vector< vector<int> > Grafo :: floyd(){
 vector< vector<int> > path = this->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;
 }

Aplicaciones

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

• 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 pseudocódigo 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.

Enlaces externos

• Implementación en C (en inglés).
• Implementación en C#
• Implementación en PHP
• Implementación en Java (explicación paso a paso) y explicación y applet (en inglés)
• Floyd-Warshall
• Floyd-Warshall Algorithm
• www.cs.umd.edu

Fuentes

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1º Edición). Sección 26.2, "The Floyd–Warshall algorithm".

• Floyd, Robert W. Algorithm 97: Shortest Path. Communications of the ACM.

• Kleene, S. C. (1956 Representation of events in nerve nets and finite automata. En C. E. Shannon and John McCarthy. Automata Studies.

• Warshall, Stephen.A theorem on Boolean matrices.

• Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5ª Edición. Addison Wesley.