Algoritmo de Floyd-Warshall

Algoritmo en la teoría de grafos

En informática , el algoritmo 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 los caminos más cortos en un grafo ponderado dirigido con pesos de arista positivos o negativos (pero sin ciclos negativos). ^{[1] [2]} Una sola ejecución del algoritmo encontrará las longitudes (pesos sumados) de los caminos más cortos entre todos los pares de vértices. Aunque no devuelve detalles de los caminos en sí, es posible reconstruir los caminos con modificaciones simples al algoritmo. También se pueden usar versiones del algoritmo para encontrar el cierre transitivo de una relación o (en conexión con el sistema de votación de Schulze ) los caminos más anchos entre todos los pares de vértices en un grafo ponderado. ${\displaystyle R}$

Historia y denominación

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] para 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 Floyd-Warshall compara muchos caminos posibles a través del grafo entre cada par de vértices. Garantiza la búsqueda de todos los caminos más cortos y puede hacerlo con comparaciones en un grafo, ^{[1] [9]} incluso aunque pueda haber aristas en el grafo. Lo hace mejorando de manera incremental una estimación del camino más corto entre dos vértices, hasta que la estimación sea óptima. ${\displaystyle \Theta (|V|^{3})}$ ${\displaystyle \Theta (|V|^{2})}$

Consideremos un gráfico con vértices numerados del 1 al  . Consideremos además una función que devuelve la longitud del camino más corto posible (si existe uno) desde hasta utilizando solo vértices del conjunto como puntos intermedios a lo largo del camino. Ahora, dada esta función, nuestro objetivo es encontrar la longitud del camino más corto desde cada uno hasta cada uno utilizando cualquier vértice en . Por definición, este es el valor , que encontraremos recursivamente . ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle N}$ ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \{1,2,\ldots ,k\}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \{1,2,\ldots ,N\}}$ ${\displaystyle \mathrm {shortestPath} (i,j,N)}$

Observe que debe ser menor o igual que : tenemos más flexibilidad si se nos permite usar el vértice . Si de hecho es menor que , entonces debe haber un camino desde hasta usando los vértices que sea más corto que cualquier camino que no use el vértice . Como no hay ciclos negativos, este camino se puede descomponer como: ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$ ${\displaystyle k}$ ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \{1,2,\ldots ,k\}}$ ${\displaystyle k}$

(1) una ruta desde hasta que utiliza los vértices , seguido de ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle \{1,2,\ldots ,k-1\}}$

(2) una ruta de a que utiliza los vértices . ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle \{1,2,\ldots ,k-1\}}$

Y, por supuesto, estos deben ser el camino más corto (o varios), de lo contrario podríamos reducir aún más la longitud. En otras palabras, hemos llegado a la fórmula recursiva:

${\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}}$.

El caso base está dado por

${\displaystyle \mathrm {shortestPath} (i,j,0)=w(i,j),}$

donde denota el peso del borde de a si existe y ∞ (infinito) en caso contrario. ${\displaystyle w(i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$

Estas fórmulas son el núcleo del algoritmo Floyd-Warshall. El algoritmo funciona calculando primero para todos los pares , luego , luego , y así sucesivamente. Este proceso continúa hasta que , y hemos encontrado la ruta más corta para todos los pares utilizando cualquier vértice intermedio. A continuación, se incluye el pseudocódigo para esta versión básica. ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ ${\displaystyle (i,j)}$ ${\displaystyle k=0}$ ${\displaystyle k=1}$ ${\displaystyle k=2}$ ${\displaystyle k=N}$ ${\displaystyle (i,j)}$

Pseudocódigo

sea ​​dist una matriz |V| × |V| de distancias mínimas inicializadas a ∞ (infinito) para cada arista ( u , v ) do dist[ u ][ v ] ← w( u , v ) // El 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 de la izquierda a continuación:

Antes de la primera recursión del bucle externo, etiquetada k = 0 arriba, los únicos caminos conocidos corresponden a los bordes individuales en el grafo. En k = 1 , se encuentran los caminos que pasan por el vértice 1: en particular, se encuentra el camino [2,1,3], que reemplaza al camino [2,3] que tiene menos bordes pero es más largo (en términos de peso). En k = 2 , se encuentran los caminos que pasan por los vértices {1,2}. Los cuadros rojo y azul muestran cómo se ensambla el camino [4,2,1,3] a partir de los dos caminos conocidos [4,2] y [2,1,3] encontrados 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 desde 2 hasta 3. En k = 3 , se encuentran los caminos que pasan por los vértices {1,2,3}. 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á:

Comportamiento con ciclos negativos

Un ciclo negativo es un ciclo cuyos bordes suman un valor negativo. No existe un camino más corto entre cualquier par de vértices que formen parte de un ciclo negativo, porque las longitudes de los caminos desde hasta pueden ser arbitrariamente pequeñas (negativas). Para obtener un resultado numéricamente significativo, el algoritmo Floyd-Warshall supone que no hay ciclos negativos. Sin embargo, si hay ciclos negativos, se puede utilizar el algoritmo Floyd-Warshall para detectarlos. La intuición es la siguiente: ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$

• El algoritmo Floyd-Warshall revisa iterativamente las longitudes de las rutas entre todos los pares de vértices , incluido donde ; ${\displaystyle (i,j)}$ ${\displaystyle i=j}$
• Inicialmente, la longitud del camino es cero; ${\displaystyle (i,i)}$
• Un camino sólo puede mejorar esto si tiene una longitud menor que cero, es decir, denota un ciclo negativo; ${\displaystyle [i,k,\ldots ,i]}$
• Por lo tanto, después del algoritmo, será negativo si existe una ruta de longitud negativa desde atrás hasta . ${\displaystyle (i,i)}$ ${\displaystyle i}$ ${\displaystyle i}$

Por lo tanto, para detectar ciclos negativos utilizando el algoritmo Floyd-Warshall, uno puede inspeccionar la diagonal de la matriz de ruta, y la presencia de un número negativo indica que el gráfico 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 , donde es el valor absoluto más grande de un borde negativo en el gráfico. Para evitar problemas de desbordamiento/desbordamiento insuficiente, uno debe verificar si hay 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, un paseo cerrado) que involucra sus vértices incidentes. Considerando todos los bordes del gráfico de ejemplo anterior como no dirigidos, por ejemplo, la secuencia de vértices 4 – 2 – 4 es un ciclo con suma de peso −2. ${\displaystyle \Omega (\cdot 6^{n-1}w_{max})}$ ${\displaystyle w_{max}}$

Reconstrucción de trayectoria

El algoritmo 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 por almacenar la ruta real desde cada vértice hasta cada uno de los otros vértices, esto no es necesario y, de hecho, es muy costoso en términos de memoria. En cambio, podemos usar el árbol de ruta más corta , que se puede calcular para cada nodo en el tiempo usando la memoria y nos permite reconstruir de manera eficiente una ruta dirigida entre dos vértices conectados. ${\displaystyle \Theta (|E|)}$ ${\displaystyle \Theta (|V|)}$

Pseudocódigo

La matriz prev[u][v]contiene el penúltimo vértice en la ruta de ua v(excepto en el caso de prev[v][v], donde siempre contiene vincluso si no hay un bucle propio en v): ^[11]

sea ​​dist una matriz de distancias mínimas inicializadas a (infinito) sea prev una matriz de índices de vértices inicializados a nulo ${\displaystyle |V|\times |V|}$ ${\displaystyle \infty }$ ${\displaystyle |V|\times |V|}$El procedimiento  FloydWarshallWithPathReconstruction () es  para cada arista (u, v) hacer dist[u][v] ← w(u, v) // El peso de la arista (u, v) anterior[u][v] ← u para cada vértice v haz distribución[v][v] ← 0 anterior[v][v] ← v para k de 1 a |V| hacer  // 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] anterior[i][j] ← anterior[k][j]

procedimiento  Path (u, v) es  si prev[u][v] = null entonces  devuelve [] camino ← [v] mientras  u ≠ v  hacer v ← anterior[u][v] ruta.prepend(v) camino de retorno

Complejidad temporal

Sea , el número de vértices. Para hallar todos los de (para todos y ) a partir de los de se requieren operaciones. Como empezamos con y calculamos la secuencia de matrices , , , , cada una con un coste de , la complejidad temporal total del algoritmo es . ${\displaystyle n}$ ${\displaystyle |V|}$ ${\displaystyle n^{2}}$ ${\displaystyle \mathrm {shortestPath} (i,j,k)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle \mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)}$ ${\displaystyle n}$ ${\displaystyle \mathrm {shortestPath} (i,j,1)}$ ${\displaystyle \mathrm {shortestPath} (i,j,2)}$ ${\displaystyle \ldots }$ ${\displaystyle \mathrm {shortestPath} (i,j,n)}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle n\cdot \Theta (n^{2})=\Theta (n^{3})}$

Aplicaciones y generalizaciones

El algoritmo Floyd-Warshall se puede utilizar para resolver, entre otros, los siguientes problemas:

• 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 grafo no tiene ponderación y se representa mediante una matriz de adyacencia booleana . Luego, la operación de adición se reemplaza por la conjunción lógica (AND) y la operación de mínimo 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, lo que interesa es encontrar la ruta con el flujo máximo entre dos vértices. Esto significa que, en lugar de tomar mínimos como en el pseudocódigo anterior, se toman máximos. Los pesos de los bordes representan restricciones fijas sobre el flujo. Los pesos de la ruta representan cuellos de botella; por lo tanto, la operación de suma anterior se reemplaza por la operación de mínimo.
• Cálculo rápido de redes Pathfinder .
• Rutas más anchas/Rutas de ancho de banda máximo
• Cálculo de la forma canónica de matrices diferenciales (DBM)
• Calcular la similitud entre gráficos
• Cierre transitivo en grafos AND/OR/umbral. ^[14]

Implementaciones

Hay implementaciones disponibles para muchos lenguajes de programación .

• Para C++ , en la biblioteca boost::graph
• Para C# , en QuikGraph
• 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 Apache Commons
• Para JavaScript , en la biblioteca Cytoscape
• Para Julia , en el paquete Graphs.jl
• 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 los paquetes e1071 y Rfast

Comparación con otros algoritmos de ruta más corta

Para los grafos con pesos de arista no negativos, el algoritmo de Dijkstra se puede utilizar para encontrar todos los caminos más cortos desde un único vértice con tiempo de ejecución . Por lo tanto, ejecutar Dijkstra comenzando en cada vértice lleva tiempo . Como , esto produce un tiempo de ejecución en el peor de los casos de Dijkstra repetido de . Si bien esto coincide con el tiempo de ejecución asintótico en el peor de los casos del algoritmo de Floyd-Warshall, las constantes involucradas importan bastante. Cuando un grafo es denso (es decir, ), el algoritmo de Floyd-Warshall tiende a funcionar mejor en la práctica. Cuando el grafo es disperso (es decir, es significativamente más pequeño que ), Dijkstra tiende a dominar. ${\displaystyle \Theta (|E|+|V|\log |V|)}$ ${\displaystyle \Theta (|E||V|+|V|^{2}\log |V|)}$ ${\displaystyle |E|=O(|V|^{2})}$ ${\displaystyle O(|V|^{3})}$ ${\displaystyle |E|\approx |V|^{2}}$ ${\displaystyle |E|}$ ${\displaystyle |V|^{2}}$

Para gráficos dispersos con aristas negativas pero sin ciclos negativos, se puede utilizar el algoritmo de Johnson , con el mismo tiempo de ejecución asintótico que el enfoque de Dijkstra repetido.

También se conocen algoritmos que utilizan la multiplicación rápida de matrices 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 requerir 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

1. 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.Véase 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 trayectorias en gráficos dirigidos", págs. 570-576.
2. Kenneth H. Rosen (2003). Matemática discreta y sus aplicaciones, quinta edición . Addison Wesley. ISBN 978-0-07-119881-3.
3. Floyd, Robert W. (junio de 1962). "Algoritmo 97: camino más corto". Comunicaciones de la ACM . 5 (6): 345. doi : 10.1145/367766.368168 . S2CID  2003382.
4. Roy, Bernard (1959). "Transitivité et connexité". CR Acad. Ciencia. París (en francés). 249 : 216–218.
5. Warshall, Stephen (enero de 1962). "Un teorema sobre matrices booleanas". Revista de la ACM . 9 (1): 11–12. doi : 10.1145/321105.321107 . S2CID  33763989.
6. Weisstein, Eric W. "Algoritmo de Floyd-Warshall". MathWorld .
7. Kleene, SC (1956). "Representación de eventos en redes nerviosas y autómatas finitos". En CE Shannon y J. McCarthy (ed.). Automata Studies . Princeton University Press. págs. 3–42.
8. Ingerman, Peter Z. (noviembre de 1962). "Algoritmo 141: Matriz de trayectorias". Comunicaciones de la ACM . 5 (11): 556. doi : 10.1145/368996.369016 . S2CID  29010500.
9. Hochbaum, Dorit (2014). "Sección 8.9: Algoritmo Floyd-Warshall para todos los pares de caminos más cortos" (PDF) . Apuntes de clase para IEOR 266: Algoritmos de grafos y flujos de red . Departamento de Ingeniería Industrial e Investigación de Operaciones, Universidad de California, Berkeley . págs. 41–42.
10. Stefan Hougardy (abril de 2010). "El algoritmo Floyd–Warshall en grafos con ciclos negativos". Information Processing Letters . 110 (8–9): 279–281. doi :10.1016/j.ipl.2010.02.001.
11. "Libro de algoritmos gratuitos".
12. Gross, Jonathan L.; Yellen, Jay (2003), Manual de teoría de grafos, matemáticas discretas y sus aplicaciones, CRC Press, pág. 65, ISBN 9780203490204.
13. Penaloza, Rafael. "Estructuras algebraicas para clausura transitiva". CiteSeerX 10.1.1.71.7650 .  {{cite journal}}: Requiere citar revista |journal=( ayuda )
14. Gillies, Donald (1993). Programación de tareas con restricciones de precedencia AND/OR (Tesis doctoral, Apéndice B) (PDF) (Informe).
15. Zwick, Uri (mayo de 2002), "Todos los pares de caminos más cortos utilizando conjuntos puente y multiplicación de matrices rectangulares", Journal of the ACM , 49 (3): 289–317, arXiv : cs/0008011 , doi :10.1145/567112.567114, S2CID  1065901.
16. Chan, Timothy M. (enero de 2010), "Más algoritmos para 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 Múnich)