Algoritmo de Floyd-Warshall

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de abril de 2020; las comprobaciones requieren 13 ediciones .

Algoritmo de Floyd-Warshall

Lleva el nombre de	Robert Floyd y Stephen Warshall
Autor	Bernardo Roy [d]
objetivo	buscar en un gráfico los caminos más cortos entre cualquier par de vértices
Estructura de datos	grafico
peor momento	${\ estilo de visualización \ Theta (\| V \| ^ {3})}$
Mejor tiempo	${\ estilo de visualización \ Theta (\| V \| ^ {3})}$
Tiempo promedio	${\ estilo de visualización \ Theta (\| V \| ^ {3})}$
costo de memoria	${\ estilo de visualización \ Theta (\| V \| ^ {2})}$
Archivos multimedia en Wikimedia Commons

En informática , el algoritmo de Floyd-Warshall (también conocido como algoritmo de Floyd , algoritmo de Roy-Warshall, algoritmo de Roy-Floyd o algoritmo WFI ) es un algoritmo para encontrar las rutas más cortas en un gráfico ponderado con pesos de borde positivos o negativos (pero sin ciclos negativos). En una ejecución del algoritmo, se encontrarán las longitudes (pesos totales) de los caminos más cortos entre todos los pares de vértices. Aunque no devuelve los detalles de las rutas en sí, es posible reconstruir las rutas con modificaciones simples al algoritmo. También se pueden usar variantes del algoritmo para encontrar el cierre transitivo de una relación o (en relación con el sistema de votación de Schulze ) los caminos más anchos entre todos los pares de vértices en un gráfico ponderado. $R$

Historia y naming

El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica y fue publicado en su forma ahora aceptada por Robert Floyd en 1962. Sin embargo, es esencialmente el mismo que los algoritmos publicados anteriormente por Bernard Roy en 1959 y también por Stephen Warshall en 1962 para encontrar el cierre transitivo de un gráfico, y está estrechamente relacionado con el algoritmo de Kleene (publicado en 1956) para convertir un finito determinista autómata a expresión regular . La formulación moderna del algoritmo en forma de tres bucles for anidados fue descrita por primera vez por Peter Ingerman también en 1962.

Algoritmo

Considere un gráfico con vértices numerados del 1 al . El algoritmo de Floyd-Warshall compara todos los caminos posibles a través del gráfico entre cada par de vértices. Puede hacer esto para comparaciones en el gráfico, incluso si el gráfico puede tener hasta bordes, y se verifica cada combinación de bordes. Esto se logra mejorando gradualmente la estimación del camino más corto entre dos vértices hasta que la estimación sea óptima. $GRAMO$ $V$ $norte$ ${\ estilo de visualización \ Theta (| V | ^ {3})}$ $\Omega (|V|^{2})$

A continuación, considere una función que devuelva el camino más corto posible de a usando solo vértices del conjunto como puntos intermedios a lo largo de este camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino más corto de cada a cada , usando cualquier vértice en . $\mathrm {ruta más corta} (i,j,k)$ $i$ $j$ ${\displaystyle \{1,2,\ldots,k\))$ $i$ $j$ $\{1,2,\ldots,N\}$

Para cada uno de estos pares de vértices , puede haber $\mathrm {ruta más corta} (i,j,k)$

(1) un camino que no pasa (usa solo vértices del conjunto ),

k

\{1,\ldots,k-1\}

(2) un camino que pasa por (de a y luego de a , en ambos casos solo se usan vértices intermedios en ).

k

i

k

k

j

\{1,\ldots,k-1\}

Sabemos que el mejor camino de a , que es el camino que usa solo vértices c a , se define como , y es claro que si hubiera un mejor camino de a a , entonces la longitud de este camino sería una cadena que consiste en del camino más corto de a (usando solo vértices intermedios en ) y el camino más corto de a (usando solo vértices intermedios en ). $i$ $j$ $una$ $k-1$ $\mathrm {ruta más corta} (i,j,k-1)$ $i$ $k$ $j$ $i$ $k$ $\{1,\ldots,k-1\}$ $k$ $j$ $\{1,\ldots,k-1\}$

Si es el peso de una arista entre los vértices y , podemos definirlo en términos de la siguiente fórmula recursiva : $w(i,j)$ $i$ $j$ $\mathrm {ruta más corta} (i,j,k)$

caso base

\mathrm {ruta más corta} (i,j,0)=w(i,j)

y caso recursivo

\mathrm {ruta más corta} (i,j,k)=

\mathrm {min} {\Big (}\mathrm {ruta más corta} (i,j,k-1),

{\displaystyle \mathrm {ruta más corta} (i,k,k-1)+\mathrm {ruta más corta} (k,j,k-1){\Big )))

Esta fórmula constituye la base del algoritmo de Floyd-Warshall. El algoritmo funciona calculando primero para todos los pares de , y luego , y así sucesivamente. Este proceso continúa hasta que se encuentra el camino más corto para todos los pares que utilizan vértices intermedios. El pseudocódigo para esta versión base es el siguiente: $\mathrm {ruta más corta} (i,j,k)$ $(yo, j)$ $k=1$ $k=2$ ${\ estilo de visualización k = N}$ $(yo, j)$

sea dist una |V| × |V| matriz de distancias mínimas inicializadas como ∞ (infinito) para cada arista ( u , v ) do dist[ u ][ v ] ← w( u , v ) // Peso de la arista ( u , v ) para cada vértice v do dist[ v ][ v ] ← 0 para k de 1 a |V| para i de 1 a |V| para j de 1 a |V| si dist[ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ] dist[ i ][ j ] ← dist[ i ][ k ] + dist[ k ][ j ] fin si

Ejemplo

El algoritmo anterior se ejecuta en el gráfico en la parte inferior izquierda:

Hasta la primera recursión del bucle exterior, denotada anteriormente por k = 0, los únicos caminos conocidos corresponden a los bordes individuales del gráfico. Para k = 1, se encuentran caminos que pasan por el vértice 1: en particular, se encuentra el camino [2,1,3], reemplazando al camino [2,3], que tiene menos aristas pero es más largo (en términos de peso ). Para k = 2, se encuentran caminos que pasan por los vértices 1,2. Los cuadros rojo y azul muestran cómo se ensambla la ruta [4,2,1,3] a partir de las dos rutas conocidas [4,2] y [2,1,3] encontradas en iteraciones anteriores, con 2 en la intersección. El camino [4,2,3] no se considera porque [2,1,3] es el camino más corto encontrado hasta ahora de 2 a 3. Para k = 3, se encuentran caminos que pasan por los vértices 1,2,3. Finalmente, para k = 4, se encuentran todos los caminos más cortos.

La matriz de distancias en cada iteración k, distancias actualizadas en negrita , será:

k = 0		una	2	3	cuatro
k = 0		j
i	una	0	∞	−2	∞
	2	cuatro	0	3	∞
	3	∞	∞	0	2
	cuatro	∞	−1	∞	0

k = 1		una	2	3	cuatro
k = 1		j
i	una	0	∞	−2	∞
	2	cuatro	0	2	∞
	3	∞	∞	0	2
	cuatro	∞	−1	∞	0

k = 2		una	2	3	cuatro
k = 2		j
i	una	0	∞	−2	∞
	2	cuatro	0	2	∞
	3	∞	∞	0	2
	cuatro	3	−1	una	0

k = 3		una	2	3	cuatro
k = 3		j
i	una	0	∞	−2	0
	2	cuatro	0	2	cuatro
	3	∞	∞	0	2
	cuatro	3	−1	una	0

k = 4		una	2	3	cuatro
k = 4		j
i	una	0	−1	−2	0
	2	cuatro	0	2	cuatro
	3	5	una	0	2
	cuatro	3	−1	una	0

Comportamiento con ciclos negativos

Un ciclo negativo es un ciclo cuya suma de aristas es negativa. No existe el camino más corto entre cualquier par de vértices , , que son parte de un ciclo negativo, porque la longitud del camino desde hasta puede ser arbitrariamente pequeña (negativa). Para una salida numéricamente significativa, el algoritmo de Floyd-Warshall asume que no hay ciclos negativos. Sin embargo, si hay ciclos negativos, se puede utilizar el algoritmo de Floyd-Warshall para detectarlos. Obviamente el algoritmo es el siguiente: $i$ $j$ $i$ $j$

El algoritmo de Floyd-Warshall analiza iterativamente la longitud del camino

entre todos los pares de vértices , incluidos aquellos donde ; $(yo, j)$ $yo=j$

Inicialmente, la longitud del camino es cero; ${\ estilo de visualización (i, i)}$
Un camino solo puede mejorar si su longitud es ${\ estilo de visualización [i, k, \ ldots, i]}$

menor que cero, es decir denota un ciclo negativo;

Así, después del algoritmo, será negativo si ${\ estilo de visualización (i, i)}$

hay un camino de longitud negativa de a . $i$ $i$

Por lo tanto, para detectar ciclos negativos utilizando el algoritmo de Floyd-Warshall, se puede verificar la diagonal de la matriz del camino más corto, y la presencia de un número negativo indica que el gráfico contiene al menos un ciclo negativo. Durante la ejecución del algoritmo, si hay un ciclo negativo, pueden aparecer números exponencialmente grandes, hasta , donde es el mayor valor absoluto de un borde negativo en el gráfico. Para evitar problemas de desbordamiento/subdesbordamiento, debe buscar números negativos en la diagonal de la matriz de ruta más corta dentro del bucle for interno del algoritmo. Obviamente, en un gráfico no dirigido, un borde negativo crea un ciclo negativo (es decir, un circuito cerrado) que incluye sus vértices incidentes. Considerando todos los bordes del ejemplo del gráfico anterior como no dirigidos, por ejemplo, la secuencia de vértices 4 - 2 - 4 es un ciclo con una suma de peso de - 2. $\Omega (\cdot 6^{n-1}w_{max})$ ${\ Displaystyle w_ {máx})$

Reconstrucción de pistas

El algoritmo de Floyd-Warshall generalmente proporciona solo longitudes de camino entre todos los pares de vértices. Con modificaciones simples, se puede crear un método para reconstruir la ruta real entre dos vértices de puntos finales cualesquiera. Si bien uno podría estar inclinado a almacenar 3 rutas reales de cada vértice a cualquier otro vértice, esto no es necesario y en realidad es muy costoso en términos de memoria. En su lugar, se puede calcular un árbol de la ruta más corta para cada nodo en el tiempo, utilizando la memoria para almacenar cada árbol, lo que nos permite reconstruir de manera eficiente una ruta a partir de dos vértices conectados. ${\ estilo de visualización \ Theta (|E|)}$ ${\ estilo de visualización \ Theta (| V |)}$

Pseudocódigo [1]

sea dist una matriz de distancias mínimas inicializadas en (infinito) sea next una matriz de índices de vértice inicializados en nulo

{\ estilo de visualización | V | \ veces | V |}

\infty

{\ estilo de visualización | V | \ veces | V |}

El procedimiento FloydWarshallWithPathReconstruction () es para cada borde (u, v) do dist[u][v] ← w(u, v) // Peso del borde (u, v) siguiente[u][v] ← v para cada vértice v do dist[ v ][ v ] ← 0 siguiente[v][v] ← v para k de 1 a |V| do // implementación estándar del algoritmo de Floyd-Warshall para i de 1 a |V| para j de 1 a |V| si dist[i][j] > dist[i][k] + dist[k][j] entonces dist[i][j] ← dist[i][k] + dist[k][j] siguiente[i][j] ← siguiente[i][k] ruta del procedimiento (u, v) si el siguiente [u] [v] = nulo , entonces devuelve [] camino = [u] mientras tu ≠ v tu ← siguiente[u][v] agregar ruta (u) camino de regreso

Análisis de Complejidad del Algoritmo

Sea el número de vértices. Para encontrar todos de (para todos y ) de requiere operaciones. Dado que comenzamos con y calculamos la secuencia de matrices , , , , el número total de operaciones utilizadas es . Por lo tanto, la complejidad del algoritmo es . $norte$ $|V|$ $n^{2}$ $\mathrm {ruta más corta} (i,j,k)$ $i$ $j$ $\mathrm {ruta más corta} (i,j,k-1)$ $2n^{2}$ $\mathrm {ruta más corta} (i,j,0)=\mathrm {edgeCost} (i,j)$ $norte$ $\mathrm {ruta más corta} (i,j,1)$ $\mathrm {ruta más corta} (i,j,2)$ $\ldots$ $\mathrm {ruta más corta} (i,j,n)$ ${\displaystyle n\cdot 2n^{2}=2n^{3))$

Aplicaciones y generalizaciones

El algoritmo de Floyd-Warshall se puede utilizar para resolver los siguientes problemas, en particular:

Caminos más cortos en grafos dirigidos (algoritmo de Floyd).
Cierre transitivo de grafos dirigidos (algoritmo de Warshall). En la formulación original del algoritmo de Warshall, el gráfico no está ponderado y está representado por una matriz de adyacencia booleana. Luego, la operación de suma se reemplaza por una conjunción lógica (AND), y la operación mínima se reemplaza por una disyunción lógica (OR).
Encontrar una expresión regular que denote un lenguaje regular aceptado por un autómata finito ( algoritmo de Kleene , una generalización estrechamente relacionada con el algoritmo de Floyd-Warshall)
Inversión de matriz real ( algoritmo de Gauss-Jordan )
Enrutamiento óptimo. En esta aplicación, debe encontrar la ruta con el flujo máximo entre dos vértices. Esto significa que en lugar de tomar los mínimos, como en el pseudocódigo anterior, se usan los máximos. Los pesos de borde representan las restricciones fijas en el flujo. Los pesos de ruta son cuellos de botella, por lo que la operación de suma anterior se reemplaza por la operación mínima.
Cálculo rápido de redes Pathfinder .
Rutas más anchas/Rutas de rendimiento máximo
Cálculo de la forma canónica de matrices de límites de diferencia (DBM)
Cálculo de la similitud entre gráficos

Implementaciones

Para C++ , en la biblioteca boost::graph
Para C# , en QuickGraph
Para C# , en QuickGraphPCL (una bifurcación de QuickGraph con mejor compatibilidad con proyectos que usan bibliotecas de clases portátiles).
Para Java , en la biblioteca de gráficos de Apache Commons
Para JavaScript , en la biblioteca de Cytoscape
Para MATLAB , en el paquete Matlab_bgl
Para Perl , en el módulo Graph
Para Python , en la biblioteca SciPy (módulo scipy.sparse.csgraph ) o en la biblioteca NetworkX
Para R , en paquete e1071 y Rfast

Comparación con otros algoritmos

El algoritmo de Floyd-Warshall es eficiente para calcular todos los caminos más cortos en gráficos densos cuando hay muchos pares de aristas entre pares de vértices. En el caso de gráficos dispersos con aristas de peso no negativo, la mejor opción es utilizar el algoritmo de Dijkstra para cada nodo posible. Con esta elección, la complejidad es cuando se usa un montón binario , que es mejor que el algoritmo de Floyd-Warshall cuando es significativamente menor (la condición de escasez de gráfico). Si el gráfico es disperso, tiene aristas con peso negativo y no hay ciclos con peso total negativo, entonces se utiliza el algoritmo de Johnson , que tiene la misma complejidad que la variante con el algoritmo de Dijkstra. $O(|V|\cdot |E|\log |V|)$ $O(|V|^{3})$ $|E|$ ${\ estilo de visualización | V | ^ {2}}$

También se conocen algoritmos que utilizan algoritmos de multiplicación de matrices rápidas , que aceleran los cálculos en gráficos densos, pero suelen tener limitaciones adicionales (por ejemplo, representar los pesos de los bordes como pequeños enteros) [2] [3] . Al mismo tiempo, debido al gran factor de tiempo de ejecución constante, la ventaja computacional sobre el algoritmo de Floyd-Warshall aparece solo en gráficos grandes.

Notas

↑ Libro gratuito de algoritmos . Consultado el 19 de diciembre de 2020. Archivado desde el original el 12 de enero de 2021. (indefinido)
↑ Zwick, Uri (mayo de 2002), Todos los pares de caminos más cortos usando conjuntos puente y multiplicación de matrices rectangulares , Journal of the ACM Vol. 49 (3): 289–317 , DOI 10.1145/567112.567114 .
↑ Chan, Timothy M. (enero de 2010), Más algoritmos para todos los pares de rutas más cortas en gráficos ponderados , SIAM Journal on Computing Vol. 39 (5): 2075–2089 , DOI 10.1137/08071990x .

Literatura

Levitin A. V. Capítulo 11. Superación de restricciones: el método de bisección // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 349-353. — 576 pág. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmos: construcción y análisis = Introducción a los Algoritmos. - 2ª ed. - M. : Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .
Belousov A. I., Tkachev S. B. Matemáticas discretas. - M. : MGTU, 2006. - 744 p. — ISBN 5-7038-2886-4 .
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Algoritmos de búsqueda de gráficos
Métodos no informados	Búsqueda bidireccional Búsqueda de haz Primera búsqueda de amplitud lexicográfica Primera búsqueda en amplitud Buscar por criterio de coste Primera búsqueda en profundidad Búsqueda retrospectiva Buscar por subir a la cima Búsqueda limitada en profundidad Búsqueda en profundidad primero con profundización iterativa
Métodos informados	Recorte alfa beta Método de rama y límite Buscar por primera mejor coincidencia A* B* D* Encontrar un punto de transición AIF* Búsqueda recursiva en la primera mejor coincidencia SMA*
Atajos	Algoritmo de onda Algoritmo Bellman-Ford Algoritmo de Dijkstra Algoritmo de Johnson Algoritmo de Levit Algoritmo de Floyd-Warshall Búsqueda de borde
Árbol de expansión mínimo	Algoritmo de Boruvka algoritmo de Prim Algoritmo de Kruskal
Otro	Algoritmo del Museo Británico Algoritmo de Edmonds recorrido del árbol Algoritmo del vecino más cercano en el problema del viajante de comercio