En ciencias de la computación , el Floyd-Warshall algoritmo (también conocido como el algoritmo de Floyd , el algoritmo de Roy-Warshall , el algoritmo de Roy-Floyd , o el algoritmo de WFI ) es un algoritmo para la búsqueda de caminos más cortos en una dirección grafo ponderado con el flanco positivo o negativo pesos (pero sin ciclos negativos). [1] [2]Una sola ejecución del algoritmo encontrará las longitudes (pesos sumados) de las rutas más cortas entre todos los pares de vértices. Aunque no devuelve detalles de las rutas en sí, es posible reconstruir las rutas con simples modificaciones al algoritmo. Las versiones del algoritmo también se pueden utilizar para encontrar el cierre transitivo de una relación., o (en relación con el sistema de votación de Schulze ) caminos más anchos entre todos los pares de vértices en un gráfico ponderado.
Clase | Problema de la ruta más corta de todos los pares (para gráficos ponderados) |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos | |
Rendimiento medio | |
Complejidad espacial en el peor de los casos |
Historia y naming
El algoritmo Floyd-Warshall es un ejemplo de programación dinámica , y fue publicado en su forma actualmente reconocida por Robert Floyd en 1962. [3] Sin embargo, es esencialmente el mismo que los algoritmos publicados previamente por Bernard Roy en 1959 [4] y también por Stephen Warshall en 1962 [5] por encontrar el cierre transitivo de un grafo, [6] y está estrechamente relacionado con el algoritmo de Kleene (publicado en 1956) para convertir un autómata finito determinista en una expresión regular . [7] La formulación moderna del algoritmo como tres bucles for anidados fue descrita por primera vez por Peter Ingerman, también en 1962. [8]
Algoritmo
El algoritmo de Floyd – Warshall compara todas las rutas posibles a través del gráfico entre cada par de vértices. Es capaz de hacer esto con comparaciones en un gráfico, aunque puede haber hasta aristas en el gráfico, y se prueba cada combinación de aristas. Lo hace mejorando gradualmente una estimación en la ruta más corta entre dos vértices, hasta que la estimación sea óptima.
Considere una gráfica con vértices numerados del 1 al . Considere además una función que devuelve el camino más corto posible desde a usando vértices solo del conjunto como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino más corto de cada a cada usando cualquier vértice en.
Para cada uno de estos pares de vértices, el podría ser cualquiera
- (1) un camino que no pasa (solo usa vértices en el conjunto .)
o
- (2) un camino que atraviesa (de a y luego de a , ambos solo usan vértices intermedios en )
Sabemos que el mejor camino desde a que solo usa vértices mediante es definido por , y está claro que si hubiera un mejor camino desde a a , entonces la longitud de este camino sería la concatenación del camino más corto desde a (solo usando vértices intermedios en ) y el camino más corto desde a (solo usando vértices intermedios en ).
Si es el peso del borde entre vértices y , podemos definir en términos de la siguiente fórmula recursiva : el caso base es
y el caso recursivo es
- .
Esta fórmula es el corazón del algoritmo Floyd-Warshall. El algoritmo funciona por primera computación. para todos pares para , luego , y así. Este proceso continúa hasta, y hemos encontrado el camino más corto para todos pares usando cualquier vértice intermedio. El pseudocódigo para esta versión básica es el siguiente: [ ¿investigación original? ]
sea dist un | V | × | V | matriz de distancias mínimas inicializadas a ∞ (infinito) para cada borde ( u , v ) do dist [ u ] [ v ] ← w ( u , v ) // El peso del borde ( 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 de la izquierda a continuación:
Antes de la primera recursividad del bucle externo, etiquetado k = 0 arriba, las únicas rutas conocidas corresponden a los bordes únicos en el gráfico. En k = 1 , se encuentran caminos que pasan por el vértice 1: en particular, se encuentra el camino [2,1,3], reemplazando el camino [2,3] que tiene menos aristas pero es más largo (en términos de peso ). En k = 2 , se encuentran caminos que atraviesan 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. La ruta [4,2,3] no se considera, porque [2,1,3] es la ruta más corta encontrada hasta ahora de 2 a 3. En k = 3 , las rutas que atraviesan los vértices {1,2,3} se encuentran. Finalmente, en k = 4 , se encuentran todos los caminos más cortos.
La matriz de distancias en cada iteración de k , con las distancias actualizadas en negrita , será:
k = 0 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
I | 1 | 0 | ∞ | −2 | ∞ |
2 | 4 | 0 | 3 | ∞ | |
3 | ∞ | ∞ | 0 | 2 | |
4 | ∞ | −1 | ∞ | 0 |
k = 1 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
I | 1 | 0 | ∞ | −2 | ∞ |
2 | 4 | 0 | 2 | ∞ | |
3 | ∞ | ∞ | 0 | 2 | |
4 | ∞ | −1 | ∞ | 0 |
k = 2 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
I | 1 | 0 | ∞ | −2 | ∞ |
2 | 4 | 0 | 2 | ∞ | |
3 | ∞ | ∞ | 0 | 2 | |
4 | 3 | −1 | 1 | 0 |
k = 3 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
I | 1 | 0 | ∞ | −2 | 0 |
2 | 4 | 0 | 2 | 4 | |
3 | ∞ | ∞ | 0 | 2 | |
4 | 3 | −1 | 1 | 0 |
k = 4 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
I | 1 | 0 | −1 | −2 | 0 |
2 | 4 | 0 | 2 | 4 | |
3 | 5 | 1 | 0 | 2 | |
4 | 3 | −1 | 1 | 0 |
Comportamiento con ciclos negativos
Un ciclo negativo es un ciclo cuyas aristas suman un valor negativo. No existe el camino más corto entre ningún par de vértices, que forman parte de un ciclo negativo, porque las longitudes a puede ser arbitrariamente pequeño (negativo). Para una salida numéricamente significativa, el algoritmo Floyd-Warshall asume que no hay ciclos negativos. No obstante, si hay ciclos negativos, se puede utilizar el algoritmo Floyd-Warshall para detectarlos. La intuición es la siguiente:
- El algoritmo Floyd-Warshall revisa iterativamente las longitudes de ruta entre todos los pares de vértices , incluyendo donde ;
- Inicialmente, la longitud del camino es cero;
- Un sendero sólo puede mejorar esto si tiene una longitud menor que cero, es decir, denota un ciclo negativo;
- Por lo tanto, después del algoritmo, será negativo si existe una ruta de longitud negativa desde de regreso .
Por lo tanto, para detectar ciclos negativos utilizando el algoritmo de Floyd-Warshall, se puede inspeccionar la diagonal de la matriz de la trayectoria, y la presencia de un número negativo indica que la gráfica contiene al menos un ciclo negativo. [9] Durante la ejecución del algoritmo, si hay un ciclo negativo, pueden aparecer números exponencialmente grandes, tan grandes como, dónde es el valor absoluto más grande de un borde negativo en el gráfico. Para evitar problemas de desbordamiento / subdesbordamiento, se deben verificar los números negativos en la diagonal de la matriz de ruta dentro del bucle for interno del algoritmo. [10] Obviamente, en un gráfico no dirigido, un borde negativo crea un ciclo negativo (es decir, una caminata cerrada) que involucra sus vértices incidentes. Considerando que todos los bordes del gráfico de ejemplo anterior no están dirigidos, por ejemplo, la secuencia de vértices 4 - 2 - 4 es un ciclo con suma de peso −2.
Reconstrucción de caminos
El algoritmo de Floyd-Warshall normalmente solo proporciona las longitudes de las rutas entre todos los pares de vértices. Con modificaciones simples, es posible crear un método para reconstruir la ruta real entre dos vértices de punto final. Si bien uno puede inclinarse a almacenar la ruta real desde cada vértice hasta el otro vértice, esto no es necesario y, de hecho, es muy costoso en términos de memoria. En cambio, el árbol de la ruta más corta se puede calcular para cada nodo en tiempo usando memoria para almacenar cada árbol, lo que nos permite reconstruir de manera eficiente una ruta a partir de dos vértices conectados.
Pseudocódigo [11]
deja que dist sea un Matriz de distancias mínimas inicializadas a (infinito) que el próximo sea un matriz de índices de vértice inicializados a nuloprocedimiento FloydWarshallWithPathReconstruction () es para cada borde (u, v) do dist [u] [v] ← w (u, v) // El peso del borde (u, v) siguiente [u] [v] ← v para cada vértice v hacer dist [v] [v] ← 0 siguiente [v] [v] ← v para k de 1 a | V | do // implementación estándar 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]
procedimiento Ruta (u, v) si siguiente [u] [v] = nulo , devuelve [] ruta = [u] mientras que u ≠ v u ← siguiente [u] [v] ruta.append (u) camino de regreso
Análisis
Dejar ser , el número de vértices. Para encontrar todo de (para todos y ) de los de requiere operaciones. Desde que comenzamos con y calcular la secuencia de matrices , , , , el número total de operaciones utilizadas es . Por tanto, la complejidad del algoritmo es.
Aplicaciones y generalizaciones
El algoritmo Floyd-Warshall se puede utilizar para resolver los siguientes problemas, entre otros:
- Rutas más cortas en gráficos 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 la conjunción lógica (AND) y la operación mínima por la disyunción lógica (OR).
- Encontrar una expresión regular que denote el lenguaje regular aceptado por un autómata finito ( algoritmo de Kleene , una generalización estrechamente relacionada del algoritmo Floyd-Warshall) [12]
- Inversión de matrices reales ( algoritmo de Gauss-Jordan ) [13]
- Enrutamiento óptimo. En esta aplicación, uno está interesado en encontrar el camino con el flujo máximo entre dos vértices. Esto significa que, en lugar de tomar mínimos como en el pseudocódigo anterior, uno toma máximos. Los pesos de los bordes representan restricciones fijas sobre el flujo. Los pesos de ruta representan cuellos de botella; por lo que la operación de adición anterior se reemplaza por la operación mínima.
- Cálculo rápido de redes Pathfinder .
- Rutas más amplias / rutas de ancho de banda máximo
- Calcular la forma canónica de matrices unidas por diferencias (DBM)
- Calcular la similitud entre gráficos
- Cierre transitivo en gráficos Y / OR / umbral. [14]
Implementaciones
Hay implementaciones disponibles para muchos lenguajes de programación .
- 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 utilizan bibliotecas de clases portátiles).
- Para Java , en la biblioteca de gráficos de Apache Commons
- Para JavaScript , en la biblioteca 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 paquetes e1071 y Rfast
Comparación con otros algoritmos de ruta más corta
El algoritmo Floyd-Warshall es una buena opción para calcular rutas entre todos los pares de vértices en gráficos densos , en los que la mayoría o todos los pares de vértices están conectados por aristas. Para gráficos dispersos con pesos de borde no negativos, se puede obtener una complejidad asintótica más baja ejecutando el algoritmo de Dijkstra desde cada posible vértice inicial, ya que el peor tiempo de ejecución de Dijkstra repetido (usando montones de Fibonacci ) es más pequeño que el tiempo de ejecución del algoritmo Floyd-Warshall cuando es significativamente más pequeño que . Para gráficos dispersos con bordes negativos pero sin ciclos negativos, se puede usar el algoritmo de Johnson , con el mismo tiempo de ejecución asintótico que el enfoque repetido de Dijkstra.
También existen algoritmos conocidos que utilizan la multiplicación de matrices rápida para acelerar el cálculo de la ruta más corta de todos los pares en gráficos densos, pero estos suelen hacer suposiciones adicionales sobre los pesos de los bordes (como exigir que sean números enteros pequeños). [15] [16] Además, debido a los altos factores constantes en su tiempo de ejecución, solo proporcionarían una aceleración sobre el algoritmo Floyd-Warshall para gráficos muy grandes.
Referencias
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8. Ver en particular la Sección 26.2, "El algoritmo Floyd-Warshall", págs. 558–565 y la Sección 26.4, "Un marco general para resolver problemas de trayectoria en gráficas dirigidas", págs. 570–576.
- ^ Kenneth H. Rosen (2003). Matemáticas discretas y sus aplicaciones, 5ª edición . Addison Wesley. ISBN 978-0-07-119881-3.
- ^ Floyd, Robert W. (junio de 1962). "Algoritmo 97: Ruta más corta". Comunicaciones de la ACM . 5 (6): 345. doi : 10.1145 / 367766.368168 .
- ^ Roy, Bernard (1959). "Transitivité et connexité" . CR Acad. Sci. París (en francés). 249 : 216–218.
- ^ Warshall, Stephen (enero de 1962). "Un teorema sobre matrices booleanas". Revista de la ACM . 9 (1): 11-12. doi : 10.1145 / 321105.321107 .
- ^ Weisstein, Eric W. "Algoritmo Floyd-Warshall" . MathWorld .
- ^ Kleene, Carolina del Sur (1956). "Representación de eventos en redes nerviosas y autómatas finitos". En CE Shannon y J. McCarthy (ed.). Estudios de autómatas . Prensa de la Universidad de Princeton. págs. 3-42.
- ^ Ingerman, Peter Z. (noviembre de 1962). "Algoritmo 141: Matriz de ruta". Comunicaciones de la ACM . 5 (11): 556. doi : 10.1145 / 368996.369016 .
- ^ Hochbaum, Dorit (2014). "Sección 8.9: algoritmo Floyd-Warshall para todos los pares de caminos más cortos" ( PDF ) . Notas de clase para IEOR 266: algoritmos de gráficos y flujos de red . Departamento de Ingeniería Industrial e Investigación de Operaciones, Universidad de California, Berkeley .
- ^ Stefan Hougardy (abril de 2010). "El algoritmo de Floyd-Warshall en gráficos con ciclos negativos". Cartas de procesamiento de información . 110 (8–9): 279–281. doi : 10.1016 / j.ipl.2010.02.001 .
- ^ https://books.goalkicker.com/AlgorithmsBook/
- ^ Gross, Jonathan L .; Yellen, Jay (2003), Manual de teoría de grafos , Matemáticas discretas y sus aplicaciones, CRC Press, p. 65, ISBN 9780203490204.
- ^ Penaloza, Rafael. "Estructuras algebraicas para cierre transitivo". CiteSeerX 10.1.1.71.7650 . Cite journal requiere
|journal=
( ayuda ) - ^ Gillies, Donald (1993). Programación de tareas con restricciones de precedencia Y / O (Tesis de doctorado, Apéndice B) (PDF) (Informe).
- ^ Zwick, Uri (mayo de 2002), "Todos los pares de caminos más cortos utilizando conjuntos de puentes y multiplicación de matrices rectangulares", Journal of the ACM , 49 (3): 289–317, arXiv : cs / 0008011 , doi : 10.1145 / 567112.567114.
- ^ Chan, Timothy M. (enero de 2010), "Más algoritmos para las rutas más cortas de todos los pares en gráficos ponderados", SIAM Journal on Computing , 39 (5): 2075-2089, CiteSeerX 10.1.1.153.6864 , doi : 10.1137 / 08071990x.
enlaces externos
- Animación interactiva del algoritmo Floyd-Warshall
- Animación interactiva del algoritmo Floyd-Warshall (Universidad Técnica de Munich)