Algoritmo de Floyd-Warshall

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 caminos más cortos en un grafo dirigido ponderado con pesos de aristas 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 reconstruirlos con simples modificaciones 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 amplios entre todos los pares de vértices en un grafo ponderado.

El algoritmo de 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 , con la diferencia de que utiliza un semianillo min-plus . ^{[ 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 de Floyd-Warshall compara muchos caminos posibles a través del grafo entre cada par de vértices. Está garantizado que encontrará todos los caminos más cortos y es capaz de hacerlo con${\displaystyle \Theta (|V|^{3})}$comparaciones en un gráfico, ^{[ 1 ] [ 9 ]} aunque puede haber${\displaystyle \Theta (|V|^{2})}$aristas en el grafo. Lo hace mejorando incrementalmente una estimación del camino más corto entre dos vértices, hasta que la estimación sea óptima.

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

Observa que${\displaystyle \mathrm {ruta más corta} (i,j,k)}$debe ser menor o igual que${\displaystyle \mathrm {ruta más corta} (i,j,k-1)}$: tenemos más flexibilidad si se nos permite usar el vértice${\displaystyle k}$. Si${\displaystyle \mathrm {ruta más corta} (i,j,k)}$es de hecho menos que${\displaystyle \mathrm {ruta más corta} (i,j,k-1)}$, entonces debe haber un camino desde${\displaystyle i}$a${\displaystyle j}$utilizando los vértices${\displaystyle \{1,2,\ldots ,k\}}$que sea más corto que cualquier ruta de este tipo que no utilice el vértice${\displaystyle k}$Dado que no existen ciclos negativos, este camino se puede descomponer de la siguiente manera:

(1) un camino desde${\displaystyle i}$a${\displaystyle k}$que utiliza los vértices${\displaystyle \{1,2,\ldots ,k-1\}}$, seguido de

(2) un camino desde${\displaystyle k}$a${\displaystyle j}$que utiliza los vértices${\displaystyle \{1,2,\ldots ,k-1\}}$.

Y, por supuesto, debe existir un camino más corto (o varios de ellos), 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 viene dado por

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

dónde${\displaystyle w(i,j)}$denota el peso del borde de${\displaystyle i}$a${\displaystyle j}$si existe uno e ∞ (infinito) en caso contrario.

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

sea ​​dist un arreglo |V| × |V| de distancias mínimas inicializado a ∞ (infinito) para cada arista ( u , v ) hacer dist[ u ][ v ] = w( u , v ) // El peso de la arista ( u , v ) para cada vértice v hacer dist[ v ][ v ] = 0 para k desde 1 hasta |V| para i desde 1 hasta |V| para j desde 1 hasta |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 que aparece a continuación:

Antes de la primera recursión del bucle externo, etiquetado como k = 0 arriba, los únicos caminos conocidos corresponden a las aristas individuales en el grafo. 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 recuadros rojo y azul muestran cómo el camino [4,2,1,3] se construye 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 de 2 a 3. En k = 3 , se encuentran 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 cuyas aristas suman un valor negativo. No existe un camino más corto entre ningún par de vértices.${\displaystyle i}$,${\displaystyle j}$que forman parte de un ciclo negativo, porque las longitudes de los caminos desde${\displaystyle i}$a${\displaystyle j}$puede ser arbitrariamente pequeño (negativo). Para obtener resultados numéricamente significativos, el algoritmo de Floyd-Warshall asume que no existen ciclos negativos. Sin embargo, si existen ciclos negativos, el algoritmo de Floyd-Warshall puede utilizarse para detectarlos. La idea es la siguiente:

• El algoritmo de Floyd-Warshall revisa iterativamente las longitudes de los caminos entre todos los pares de vértices.${\displaystyle (i,j)}$, incluyendo dónde${\displaystyle i=j}$;
• Inicialmente, la longitud del camino${\displaystyle (i,i)}$es cero;
• Un camino${\displaystyle [i,k,\ldots ,i]}$Solo se puede mejorar esto si tiene una longitud menor que cero, es decir, denota un ciclo negativo;
• Por lo tanto, después del algoritmo,${\displaystyle (i,i)}$será negativo si existe un camino de longitud negativa desde${\displaystyle i}$volver a${\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 grafo contiene al menos un ciclo negativo. ^{[ 9 ]} Sin embargo, cuando hay un ciclo negativo presente, durante la ejecución del algoritmo se generan números exponencialmente grandes del orden de${\displaystyle \Omega (6^{n}\cdot w_{max})}$puede aparecer, donde${\displaystyle w_{max}}$es el mayor valor absoluto del peso de la arista en el grafo. Para evitar problemas de subdesbordamiento de enteros, se debe comprobar si hay un ciclo negativo dentro del bucle for más interno del algoritmo. ^{[ 11 ]}

El algoritmo de Floyd-Warshall normalmente solo proporciona las longitudes de los caminos entre todos los pares de vértices. Con modificaciones sencillas, es posible crear un método para reconstruir el camino real entre cualquier par de vértices extremos. Si bien uno podría inclinarse a almacenar el camino real de cada vértice a cada otro vértice, esto no es necesario y, de hecho, es muy costoso en términos de memoria. En su lugar, podemos usar el árbol de caminos más cortos , que se puede calcular para cada nodo en${\displaystyle \Theta (|E|)}$tiempo usando${\displaystyle \Theta (|V|)}$memoria, y nos permite reconstruir de manera eficiente un camino dirigido entre dos vértices conectados cualesquiera.

que esto sea un${\displaystyle |V|\times |V|}$matriz de distancias mínimas inicializadas a${\displaystyle \infty }$(infinito) sea prev un${\displaystyle |V|\times |V|}$matriz de índices de vértices inicializada a nuloEl procedimiento FloydWarshallWithPathReconstruction () es para cada arista (u, v) hacer dist[u][v] = w(u, v) // El peso de la arista (u, v) prev[u][v] = u para cada vértice v hacer dist[v][v] = 0 prev[v][v] = v para k desde 1 hasta |V| hacer // implementación estándar de Floyd-Warshall para i desde 1 hasta |V| para j desde 1 hasta |V| si dist[i][j] > dist[i][k] + dist[k][j] entonces dist[i][j] = dist[i][k] + dist[k][j] prev[i][j] = prev[k][j]

El procedimiento Path (u, v) es si prev[u][v] = null entonces devuelve [] ruta = [v] mientras u ≠ v hacer v = prev[u][v] ruta.anteponer(v) ruta de retorno

Dejar${\displaystyle n}$ser${\displaystyle |V|}$, el número de vértices. Para encontrar todos${\displaystyle n^{2}}$de ${\displaystyle \mathrm {shortestPath} (i,j,k)}$(a pesar de${\displaystyle i}$y${\displaystyle j}$) de aquellos de ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$requiere${\displaystyle \Theta (n^{2})}$operaciones. Dado que comenzamos con ${\displaystyle \mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)}$y calcular la secuencia de${\displaystyle n}$matrices${\displaystyle \mathrm {shortestPath} (i,j,1)}$,${\displaystyle \mathrm {shortestPath} (i,j,2)}$,${\displaystyle \ldots }$,${\displaystyle \mathrm {shortestPath} (i,j,n)}$, cada uno con un costo de${\displaystyle \Theta (n^{2})}$, la complejidad temporal total del algoritmo es${\displaystyle n\cdot \Theta (n^{2})=\Theta (n^{3})}$. ^{[ 9 ] [ 13 ]}

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

• 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 . La operación de suma 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 de Floyd-Warshall) ^{[ 14 ]}
• Inversión de matrices reales ( algoritmo de Gauss-Jordan ) ^{[ 15 ]}
• Enrutamiento óptimo. En esta aplicación, el objetivo es encontrar la ruta con el máximo flujo 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 las aristas representan restricciones fijas al flujo. Los pesos de las rutas 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 máximo ancho de banda
• Cálculo de la forma canónica de las matrices de límites de diferencias (DBM)
• Calcular la similitud entre grafos
• Cierre transitivo en grafos AND/OR/umbral. ^{[ 16 ]}

Existen 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 Apache Commons Graph
• Para JavaScript , en la biblioteca Cytoscape
• Para Julia , en el paquete Graphs.jl
• Para MATLAB , en el paquete Matlab_bgl archivado el 17 de agosto de 2013 en Wayback Machine
• 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 C , una implementación paralela con pthreads que incluye una interfaz SQLite para los datos en floydWarshall.h

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

Para grafos 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 método 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 entre todos los pares de nodos en grafos densos, pero estos suelen hacer suposiciones adicionales sobre los pesos de las aristas (como requerir que sean enteros pequeños). ^{[ 17 ] [ 18 ]} Además, debido a los altos factores constantes en su tiempo de ejecución, solo proporcionarían una mejora de velocidad con respecto al algoritmo de Floyd-Warshall para grafos muy grandes.

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