Algoritmo de Floyd-WarshallEn 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.

Índice

1 Algoritmo 2 Pseudocodigo 3 Código en C++ 4 Comportamiento con ciclos negativos 5 Ejemplo 6 Análisis 7 Aplicaciones y generalizaciones 8 Implementación del algoritmo de Floyd-Warshall 9 Referencias 10 Véase también 11 Enlaces externos

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 comparaciones (esto es notable considerando que puede haber hasta 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 con conjunto de vértices , numerados de 1 a N. Sea además una función

que devuelve el camino mínimo de a usando únicamente los vértices de 1 a como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada a cada usando únicamente los vértices de 1 hasta .

Hay dos candidatos para este camino: un camino mínimo, que utiliza únicamente los vértices del conjunto

; o bien existe un camino que va desde hasta , y de hasta , que es mejor. Sabemos que el camino óptimo de a que únicamente utiliza los vértices de 1 hasta está definido por

, y está claro que si hubiera un camino mejor de a a , la longitud de este

camino sería la concatenación del camino mínimo de a (utilizando vértices de ) y el camino

mínimo de a (que también utiliza los vértices en ).

Por lo tanto, podemos definir de forma recursiva:

Esta fórmula es la base del algoritmo Floyd-Warshall. Funciona ejecutando primero

para todos los pares , usándolos para después hallar

para todos los pares ... Este proceso continúa hasta que , y habremos

encontrado el camino más corto para todos los pares de vértices 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 j2 (infinito si no existe).3 También suponemos que es el número de vértices y pesoArista(i,i) = 04 */56 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 pesoArista(i,j)10 */1112 procedimiento FloydWarshall ()13 para k: = 0 hasta n − 114 para todo (i,j) en (0..n − 1)15 camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j])16 fin para17 fin para

Código en C++

// Declaraciones en el archivo .hint cn; //cantidad de nodosvector< vector<int> > ady; // Devuelve una matriz con las distancias minimas de cada nodo al resto de los vertices.vector< vector<int> > Grafo :: floydWarshall(){ 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;}