Algoritmo Floyd – Warshall - Floyd–Warshall algorithm

Algoritmo de Floyd-Warshall

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	${\ Displaystyle \ Theta (| V | ^ {3})}$
Rendimiento en el mejor de los casos	${\ Displaystyle \ Theta (| V | ^ {3})}$
Rendimiento medio	${\ Displaystyle \ Theta (| V | ^ {3})}$
Complejidad espacial en el peor de los casos	${\ Displaystyle \ Theta (| V | ^ {2})}$

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). 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 ) las rutas más amplias entre todos los pares de vértices en un gráfico ponderado. ${\ Displaystyle R}$

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. Sin embargo, es esencialmente el mismo que los algoritmos publicados previamente por Bernard Roy en 1959 y también por Stephen Warshall en 1962 para encontrar el cierre transitivo de un gráfico, y está estrechamente relacionado con el algoritmo de Kleene (publicado en 1956) para convertir un autómata finito determinista en una expresión regular . La formulación moderna del algoritmo como tres bucles for anidados fue descrita por primera vez por Peter Ingerman, también en 1962.

Algoritmo

El algoritmo de Floyd – Warshall compara todas las rutas posibles a través del gráfico entre cada par de vértices. Puede hacer esto con comparaciones en un gráfico, aunque puede haber hasta bordes en el gráfico, y se prueba cada combinación de bordes. Lo hace mejorando gradualmente una estimación en la ruta más corta entre dos vértices, hasta que la estimación sea óptima. ${\ Displaystyle \ Theta (| V | ^ {3})}$${\ Displaystyle \ Omega (| V | ^ {2})}$

Considere una gráfica con vértices numerados del 1 al  . Considere además una función que devuelve la ruta más corta posible 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 el camino más corto de cada uno a cada uno usando cualquier vértice en . ${\ Displaystyle G}$${\ Displaystyle V}$${\ Displaystyle N}$${\ Displaystyle \ mathrm {ruta más corta} (i, j, k)}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle \ {1,2, \ ldots, k \}}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle \ {1,2, \ ldots, N \}}$

Para cada uno de estos pares de vértices, el podría ser ${\ Displaystyle \ mathrm {ruta más corta} (i, j, k)}$

(1) una ruta que no atraviesa (solo usa vértices en el conjunto ).${\ Displaystyle k}$${\ Displaystyle \ {1, \ ldots, k-1 \}}$

o

(2) una ruta que atraviesa (de a y luego de a , ambos solo usan vértices intermedios en  )${\ Displaystyle k}$${\ Displaystyle i}$${\ Displaystyle k}$${\ Displaystyle k}$${\ Displaystyle j}$${\ Displaystyle \ {1, \ ldots, k-1 \}}$

Sabemos que la mejor ruta de a que solo usa vértices a través está definida por , y está claro que si hubiera una mejor ruta de a a , entonces la longitud de esta ruta sería la concatenación de la ruta más corta de a (solo usando vértices intermedios en ) y la ruta más corta de a (solo usando vértices intermedios en  ). ${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle 1}$${\ Displaystyle k-1}$${\ Displaystyle \ mathrm {ruta más corta} (i, j, k-1)}$${\ Displaystyle i}$${\ Displaystyle k}$${\ Displaystyle j}$${\ Displaystyle i}$${\ Displaystyle k}$${\ Displaystyle \ {1, \ ldots, k-1 \}}$${\ Displaystyle k}$${\ Displaystyle j}$${\ Displaystyle \ {1, \ ldots, k-1 \}}$

Si es el peso de la arista entre vértices y , podemos definir en términos de la siguiente fórmula recursiva : el caso base es ${\ Displaystyle w (i, j)}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle \ mathrm {ruta más corta} (i, j, k)}$

${\ Displaystyle \ mathrm {ruta más corta} (i, j, 0) = w (i, j)}$

y el caso recursivo es

${\ Displaystyle \ mathrm {ruta más corta} (i, j, k) =}$

${\ Displaystyle \ mathrm {min} {\ Big (} \ mathrm {ruta más corta} (i, j, k-1),}$

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

Esta fórmula es el corazón del algoritmo Floyd-Warshall. El algoritmo funciona calculando primero todos los pares para , luego , y así sucesivamente. Este proceso continúa hasta que hayamos encontrado el camino más corto para todos los pares usando cualquier vértice intermedio. A continuación, se muestra el pseudocódigo para esta versión básica: ${\ Displaystyle \ mathrm {ruta más corta} (i, j, k)}$${\ Displaystyle (i, j)}$${\ Displaystyle k = 1}$${\ Displaystyle k = 2}$${\ Displaystyle k = N}$${\ Displaystyle (i, j)}$

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

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

Comportamiento con ciclos negativos

Un ciclo negativo es un ciclo cuyas aristas suman un valor negativo. No hay una ruta más corta entre ningún par de vértices , que forman parte de un ciclo negativo, porque las longitudes de las rutas de a pueden ser arbitrariamente pequeñas (negativas). 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: ${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle i}$${\ Displaystyle j}$

• El algoritmo Floyd-Warshall revisa iterativamente las longitudes de ruta 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 solo 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 la trayectoria, y la presencia de un número negativo indica que la gráfica contiene al menos un ciclo negativo. 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 / subdesbordamiento, se deben verificar los números negativos en la diagonal de la matriz de ruta dentro del bucle for interno del algoritmo. 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. ${\ Displaystyle \ Omega (\ cdot 6 ^ {n-1} w_ {max})}$${\ Displaystyle w_ {max}}$

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 el tiempo utilizando 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

let dist be a ${\displaystyle |V|\times |V|}$ array of minimum distances initialized to ${\displaystyle \infty }$ (infinity)
let next be a ${\displaystyle |V|\times |V|}$ array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
        next[u][v] ← v
    for each vertex v do
        dist[v][v] ← 0
        next[v][v] ← v
    for k from 1 to |V| do // standard Floyd-Warshall implementation
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][j] > dist[i][k] + dist[k][j] then
                    dist[i][j] ← dist[i][k] + dist[k][j]
                    next[i][j] ← next[i][k]

procedure Path(u, v)
    if next[u][v] = null then
        return []
    path = [u]
    while u ≠ v
        u ← next[u][v]
        path.append(u)
    return path

Análisis

Vamos a ser , el número de vértices. Para encontrar todos los de (para todos y ) de las de los requiere operaciones. Desde comenzamos con y calculamos la secuencia de matrices , , , , el número total de operaciones utilizado es . Por tanto, la complejidad del algoritmo es . ${\ Displaystyle n}$${\ Displaystyle | V |}$${\ Displaystyle n ^ {2}}$${\ Displaystyle \ mathrm {ruta más corta} (i, j, k)}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle \ mathrm {ruta más corta} (i, j, k-1)}$${\ Displaystyle 2n ^ {2}}$${\ Displaystyle \ mathrm {ruta más corta} (i, j, 0) = \ mathrm {edgeCost} (i, j)}$${\ Displaystyle 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)}$${\ Displaystyle n \ cdot 2n ^ {2} = 2n ^ {3}}$${\ Displaystyle \ Theta (n ^ {3})}$

Aplicaciones y generalizaciones

El algoritmo de 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 de Floyd-Warshall)
• Inversión de matrices reales ( algoritmo de Gauss-Jordan )
• 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.

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 vértice inicial posible, ya que el peor tiempo de ejecución de Dijkstra repetido ( usando montones de Fibonacci ) es menor que el tiempo de ejecución del Floyd –Algoritmo de Warhall cuando es significativamente menor 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. ${\ Displaystyle O (| E || V | + | V | ^ {2} \ log | V |)}$${\ Displaystyle O (| V | ^ {3})}$${\ Displaystyle | E |}$${\ Displaystyle | V | ^ {2}}$

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). 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

enlaces externos

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