Algoritmo de Floyd-Warshall

Algoritmo de Floyd-Warshall

Clase	Problema de la ruta más corta entre todos los pares (para gráficos ponderados)
Estructura de datos	Gráfico
Rendimiento en el peor de los casos	${\displaystyle \Theta (|V|^{3})}$
Rendimiento en el mejor de los casos	${\displaystyle \Theta (|V|^{3})}$
Rendimiento promedio	${\displaystyle \Theta (|V|^{3})}$
Complejidad espacial en el peor de los casos	${\displaystyle \Theta (|V|^{2})}$

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.${\estilo de visualización R}$

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]

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 .${\estilo de visualización G}$${\estilo de visualización V}$${\estilo de visualización N}$${\displaystyle \mathrm {ruta más corta} (i,j,k)}$${\estilo de visualización i}$${\estilo de visualización j}$${\displaystyle \{1,2,\lpuntos ,k\}}$${\estilo de visualización i}$${\estilo de visualización j}$${\displaystyle \{1,2,\lpuntos ,N\}}$${\displaystyle \mathrm {ruta más corta} (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 {ruta más corta} (i,j,k)}$${\displaystyle \mathrm {ruta más corta} (i,j,k-1)}$${\estilo de visualización k}$${\displaystyle \mathrm {ruta más corta} (i,j,k)}$${\displaystyle \mathrm {ruta más corta} (i,j,k-1)}$${\estilo de visualización i}$${\estilo de visualización j}$${\displaystyle \{1,2,\lpuntos ,k\}}$${\estilo de visualización k}$

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

(2) una ruta de a que utiliza los vértices .${\estilo de visualización k}$${\estilo de visualización j}$${\displaystyle \{1,2,\lpuntos ,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 {ruta más corta} (i,j,k)=}$

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

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

El caso base está dado por

${\displaystyle \mathrm {ruta más corta} (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)}$${\estilo de visualización i}$${\estilo de visualización 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 {ruta más corta} (i,j,k)}$${\estilo de visualización (i,j)}$${\displaystyle k=0}$${\estilo de visualización k=1}$${\estilo de visualización k=2}$${\displaystyle k=N}$${\estilo de visualización (i,j)}$

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

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á:

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:${\estilo de visualización i}$${\estilo de visualización j}$${\estilo de visualización i}$${\estilo de visualización j}$

• El algoritmo Floyd-Warshall revisa iterativamente las longitudes de las rutas entre todos los pares de vértices , incluido donde ;${\estilo de visualización (i,j)}$${\displaystyle i=j}$
• Inicialmente, la longitud del camino es cero;${\estilo de visualización (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,\lpuntos ,i]}$
• Por lo tanto, después del algoritmo, será negativo si existe una ruta de longitud negativa desde atrás hasta .${\estilo de visualización (i,i)}$${\estilo de visualización i}$${\estilo de visualización 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_{máx}}$

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|)}$

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|}$${\estilo de visualización\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

Esta sección no cita ninguna fuente . Por favor, ayude a mejorar esta sección añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado . ( Agosto de 2022 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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 .${\estilo de visualización n}$${\estilo de visualización |V|}$${\estilo de visualización n^{2}}$${\displaystyle \mathrm {ruta más corta} (i,j,k)}$${\estilo de visualización i}$${\estilo de visualización j}$${\displaystyle \mathrm {ruta más corta} (i,j,k-1)}$$Estilo de visualización: \Theta (n^{2})}$${\displaystyle \mathrm {ruta más corta} (i,j,0)=\mathrm {costo de borde} (i,j)}$${\estilo de visualización n}$${\displaystyle \mathrm {ruta más corta} (i,j,1)}$${\displaystyle \mathrm {ruta más corta} (i,j,2)}$${\displaystyle \ldots}$${\displaystyle \mathrm {ruta más corta} (i,j,n)}$$Estilo de visualización: \Theta (n^{2})}$${\displaystyle n\cdot \Theta (n^{2})=\Theta (n^{3})}$

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]

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

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|\aprox |V|^{2}}$${\estilo de visualización |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.

Wikimedia Commons tiene medios relacionados con el algoritmo Floyd-Warshall .

• Animación interactiva del algoritmo Floyd-Warshall
• Animación interactiva del algoritmo Floyd-Warshall (Universidad Técnica de Múnich)