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.
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.
Luego, este resultado se verá volcado en la matriz final.
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”).
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.
* 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.
comparaciones (esto es notable considerando que puede haber hasta
, numerados de 1 a N. Sea además una función
Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada
que únicamente utiliza los vértices de 1 hasta
, y está claro que si hubiera un camino mejor de
c a m i n o
Esta fórmula es la base del algoritmo Floyd-Warshall.
c a m i n o
c a m i n o
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: 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.
Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias: 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.
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.
Si utilizamos matrices booleanas, para encontrar todos los
y puede ser resuelto por una máquina determinista de Turing en tiempo polinómico.
El algoritmo de Floyd-Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:
