Algoritmo de Floyd-Warshall

Algoritmo para encontrar caminos más cortos para todos los pares en gráficos, lo que permite que algunos pesos de los bordes sean negativos

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 caminos más cortos en un gráfico ponderado dirigido con borde positivo o negativo. pesos (pero sin ciclos negativos). ^{[1] [2]} Una única 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 las rutas en sí, es posible reconstruirlas con simples modificaciones al algoritmo. También se pueden utilizar versiones 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 amplios entre todos los pares de vértices en un gráfico 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 anteriormente por Bernard Roy en 1959 ^[4] y también por Stephen Warshall en 1962 ^[5] para encontrar el cierre transitivo de un gráfico, ^[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 gráfico entre cada par de vértices. Se garantiza que encontrará todos los caminos más cortos y puede hacerlo con comparaciones en un gráfico, aunque pueda haber bordes en el gráfico. Lo hace mejorando incrementalmente una estimación en el camino más corto entre dos vértices, hasta que la estimación sea óptima. ${\displaystyle \Theta (|V|^{3})}$ ${\displaystyle \Theta (|V|^{2})}$

Considere una gráfica con vértices numerados del 1 al  . Considere además una función que devuelve la longitud del camino más corto posible (si existe) desde hasta usando vértices solo 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 de cada uno a cada usando cualquier vértice en . Por definición, este es el valor , que encontraremos de forma recursiva . ${\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)}$

Observa 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 una ruta desde hasta usando los vértices que sea más corta que cualquier ruta 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) un camino desde hasta que utiliza los vértices . ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle \{1,2,\ldots ,k-1\}}$

Y, por supuesto, estos deben ser los caminos más cortos , 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 )}}$.

Mientras tanto, el caso base está dado por

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

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

Estas fórmulas son el corazón del algoritmo Floyd-Warshall. El algoritmo funciona calculando primero todos los pares de , luego , luego , y así sucesivamente. Este proceso continúa hasta que hayamos encontrado el camino más corto para todos los pares utilizando cualquier vértice intermedio. A continuación se muestra 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 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 recursión del bucle externo, denominado k = 0 arriba, los únicos caminos conocidos corresponden a los bordes individuales 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 pasan por los vértices {1,2}. Los cuadros rojo y azul muestran cómo la ruta [4,2,1,3] se ensambla 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. En k = 3 , los caminos que pasan por 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á:

Comportamiento con ciclos negativos

Un ciclo negativo es un ciclo cuyas aristas suman un valor negativo. No existe un camino más corto entre cualquier par de vértices , que forman parte de un ciclo negativo, porque las longitudes de los caminos desde hasta pueden ser arbitrariamente pequeñas (negativas). Para obtener resultados numéricamente significativos, el algoritmo Floyd-Warshall supone que no hay ciclos negativos. Sin embargo, si existen ciclos negativos, se puede utilizar el algoritmo de 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 los caminos entre todos los pares de vértices , incluido dónde ; ${\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 de Floyd-Warshall, se 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 mayor valor absoluto de un borde negativo en el gráfico. Para evitar problemas de desbordamiento/desbordamiento insuficiente, 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, una arista negativa crea un ciclo negativo (es decir, un recorrido cerrado) 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 pesos −2. ${\displaystyle \Omega (\cdot 6^{n-1}w_{max})}$ ${\displaystyle w_{max}}$

Reconstrucción del camino

El algoritmo Floyd-Warshall normalmente solo proporciona las longitudes de los caminos 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 cualesquiera. Si bien uno puede inclinarse por almacenar la ruta real desde cada vértice a cada otro vértice, esto no es necesario y, de hecho, es muy costoso en términos de memoria. En cambio, el árbol de ruta más corta se puede calcular para cada nodo en el tiempo usando la memoria para almacenar cada árbol, lo que nos permite reconstruir de manera eficiente una ruta a partir de dos vértices conectados. ${\displaystyle \Theta (|E|)}$ ${\displaystyle \Theta (|V|)}$

Pseudocódigo

Fuente: ^[11]

sea ​​dist una matriz de distancias mínimas inicializada 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 borde (u, v) do dist[u][v] ← w(u, v) // El peso del borde (u, v) anterior[u][v] ← u para cada vértice v hacer dist[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 Ruta (u, v) si prev[u][v] = nulo entonces  devuelve [] camino ← [v] mientras  tu ≠ v v ← anterior[u][v] ruta.anteponer(v) vía de retorno

Análisis de tiempo

Sea , el número de vértices. Para encontrar todos los de (for all y ) de los de requiere operaciones. Dado que comenzamos y calculamos la secuencia de matrices , , , , el número total de operaciones utilizadas es . Por tanto, la complejidad 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 2n^{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 n\cdot 2n^{2}=2n^{3}}$ ${\displaystyle \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 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 conjunción lógica (Y) y la operación de mínimo por disyunción lógica (O).
• 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 de 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, se toman máximos. Los pesos de los bordes representan restricciones fijas de flujo. Los pesos de ruta representan 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 ancho de banda máximo
• Calcular la forma canónica de matrices ligadas por diferencias (DBM)
• Calcular la similitud entre gráficas.
• Cierre transitivo en gráficos Y/O/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 Apache Commons Graph
• 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 Gráfico
• 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

Para gráficos con pesos de borde 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 . Dado que , 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 Floyd-Warshall, las constantes involucradas importan bastante. Cuando un gráfico es denso (es decir, ), el algoritmo Floyd-Warshall tiende a funcionar mejor en la práctica. Cuando el gráfico 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 repetido de Dijkstra.

También existen algoritmos conocidos 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 generalmente hacen 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.Consulte en particular la Sección 26.2, "El algoritmo de Floyd-Warshall", págs. 558–565 y la Sección 26.4, "Un marco general para resolver problemas de trayectoria en gráficos dirigidos", págs. 570–576.
2. Kenneth H. Rosen (2003). Matemáticas discretas 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 Floyd-Warshall". MundoMatemático .
7. 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.
8. Ingerman, Peter Z. (noviembre de 1962). "Algoritmo 141: Matriz de rutas". 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) . Notas de la conferencia para IEOR 266: Algoritmos gráficos y flujos de red . Departamento de Ingeniería Industrial e Investigación de Operaciones, Universidad de California, Berkeley .
10. Stefan Hougardy (abril de 2010). "El algoritmo 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.
11. "Libro gratuito de algoritmos".
12. Bruto, 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. Peñaloza, Rafael. "Estructuras algebraicas para cierre transitivo". CiteSeerX 10.1.1.71.7650 .  {{cite journal}}: Citar diario requiere |journal=( ayuda )
14. Gillies, Donald (1993). Programación de tareas con restricciones de precedencia Y/O (Tesis doctoral, Apéndice B) (PDF) (Reporte).
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 caminos más cortos 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)