Algoritmo de Floyd-Warshall

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Algoritmo para encontrar caminos más cortos en los gráficos, permitiendo que algunos pesos de borde sean negativos

En la informática, la Floyd–Warshall algoritmo (también conocido como El algoritmo de Floyd, el Roy-Warshall algoritmo, el Roy-Floyd algoritmo, o el WFI algoritmo) es un algoritmo para encontrar caminos más cortos en un gráfico con pesos de borde positivo o negativo (pero sin ciclos negativos). Una única ejecución del algoritmo encontrará las longitudes (pesos totales) de los caminos más cortos entre todos los pares de vértices. Aunque no devuelve detalles de los caminos mismos, es posible reconstruir los caminos con modificaciones simples al algoritmo. Versiones del algoritmo también se pueden utilizar para encontrar el cierre transitivo de una relación $R$ , o (en conexión con el sistema de votación Schulze) caminos más amplios entre todos los pares de vértices en un gráfico ponderado.

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

Considere un gráfico $G$ con vértices $V$ numeradas 1 a $N$ . Seguir considerando una función ${displaystyle mathrm {shortestPath} (i,j,k)}$ que devuelve la longitud del camino más corto posible (si existe) $i$ a $j$ usando vértices sólo del conjunto ${displaystyle {1,2,ldotsk}}$ 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 $i$ a cada uno $j$ utilizando cualquiera vértice en ${1,2,ldotsN}$ . Por definición, este es el valor ${displaystyle mathrm {shortestPath} (i,j,N)}$ , que encontraremos recursivamente.

Observe que ${displaystyle mathrm {shortestPath} (i,j,k)}$ debe ser inferior o igual a ${displaystyle mathrm {shortestPath} (i,j,k-1)}$ : tenemos más flexibilidad si se nos permite utilizar el vértice $k$ . Si ${displaystyle mathrm {shortestPath} (i,j,k)}$ es en realidad menos que ${displaystyle mathrm {shortestPath} (i,j,k-1)}$ , entonces debe haber un camino desde $i$ a $j$ usando los vértices ${displaystyle {1,2,ldotsk}}$ que es más corto que cualquier camino que no utiliza el vértice $k$ . Este camino se puede descomponer como:

(1) un camino desde

i

k

que utiliza los vértices

{displaystyle {1,2,ldotsk-1}}

, seguido

(2) un camino desde

k

j

que utiliza los vértices

{displaystyle {1,2,ldotsk-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 viene dado por

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

Donde ${displaystyle w(i,j)}$ denota el peso del borde desde $i$ a $j$ si uno existe y ∞ (infinito) de otro modo.

Estas fórmulas son el corazón del algoritmo Floyd-Warshall. El algoritmo funciona por primera computación ${displaystyle mathrm {shortestPath} (i,j,k)}$ para todos $(i,j)$ pares para $k=0$ , entonces $k=1$ , entonces $k=2$ , y así sucesivamente. Este proceso continúa hasta $k=N$ , y hemos encontrado el camino más corto para todos $(i,j)$ pares usando cualquier vértices intermedios. Pseudocode para esta versión básica sigue.

Pseudocódigo

Deja dist be a TENV SUPERVISIÓN × TENV permanente array of minimum distances initialized to ∞ (infinity)
para cada uno bordeu, v) dodist[u[ ]v← wu, v) // El peso del borde (u, v)para cada uno vertex v dodist[v[ ]v← 0
para k desde 1 a Silencio
 para i desde 1 a Silencio
 para j desde 1 a Silencio
 si dist[i[ ]j[ ]i[ ]k# + dist[k[ ]j]
dist[i[ ]j← dist[i[ ]k# + dist[k[ ]j]
 terminar 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 exterior, etiquetada como $k = 0$ arriba, las únicas rutas conocidas corresponden a los bordes individuales del gráfico. En $k = 1$ se encuentran caminos que pasan por el vértice 1: en concreto 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 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$ , se encuentran caminos que pasan por los vértices {1,2,3}. Finalmente, en $k = 4$ , se encuentran todas las rutas más cortas.

La matriz de distancia en cada iteración de $k$ , con las distancias actualizadas en negrita, ser:


$k = 0$		1	2	3	4
$k = 0$		$j$
$i$	1	0	JUEGO	−2	JUEGO
	2	4	0	3	JUEGO
	3	JUEGO	JUEGO	0	2
	4	JUEGO	−1	JUEGO	0


$k = 1$		1	2	3	4
$k = 1$		$j$
$i$	1	0	JUEGO	−2	JUEGO
	2	4	0	2	JUEGO
	3	JUEGO	JUEGO	0	2
	4	JUEGO	−1	JUEGO	0


$k = 2$		1	2	3	4
$k = 2$		$j$
$i$	1	0	JUEGO	−2	JUEGO
	2	4	0	2	JUEGO
	3	JUEGO	JUEGO	0	2
	4	3	−1	1	0


$k = 3$		1	2	3	4
$k = 3$		$j$
$i$	1	0	JUEGO	−2	0
	2	4	0	2	4
	3	JUEGO	JUEGO	0	2
	4	3	−1	1	0


$k = 4$		1	2	3	4
$k = 4$		$j$
$i$	1	0	−1	−2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	−1	1	0

Comportamiento con ciclos negativos

Un ciclo negativo es un ciclo cuyos bordes suman un valor negativo. No hay un camino más corto entre cualquier par de vértices $i$ , $j$ que forman parte de un ciclo negativo, porque las longitudes de ruta de $i$ a $j$ puede ser arbitrariamente pequeño (negativo). Para la producción numéricamente significativa, el algoritmo Floyd-Warshall supone que no hay ciclos negativos. Sin embargo, si hay ciclos negativos, el algoritmo Floyd-Warshall puede utilizarse para detectarlos. La intuición es la siguiente:

El algoritmo Floyd–Warshall revisa iterativamente las longitudes de la ruta entre todos los pares de vértices $(i,j)$ , incluyendo dónde $i=j$ ;
Inicialmente, la longitud del camino $(i,i)$ es cero;
Un camino ${displaystyle [i,k,ldotsi]}$ sólo puede mejorar sobre esto si tiene una longitud inferior a cero, es decir, denota un ciclo negativo;
Así, después del algoritmo, $(i,i)$ será negativo si existe un camino negativo de longitud $i$ volver a $i$ .

Por lo tanto, para detectar ciclos negativos utilizando el algoritmo 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. Durante la ejecución del algoritmo, si hay un ciclo negativo, pueden aparecer números exponencialmente grandes, tan grandes como ${displaystyle Omega (cdot 6^{n-1}w_{max})}$ , donde ${displaystyle w_{max}}$ es el mayor valor absoluto de un borde negativo en el gráfico. Para evitar problemas de desbordamiento/desbordamiento uno debe comprobar los números negativos en la diagonal de la matriz del camino dentro del bucle interior del algoritmo. Obviamente, en un gráfico no dirigido un borde negativo crea un ciclo negativo (es decir, un paseo cerrado) que implica sus vértices incidentales. Considerando todos los bordes del gráfico de ejemplo anterior como no dirigido, por ejemplo, la secuencia del vértice 4 – 2 – 4 es un ciclo con suma de peso −2.

Reconstrucción de rutas

El algoritmo Floyd–Warshall normalmente sólo proporciona las longitudes de los caminos entre todos los pares de vértices. Con modificaciones simples, es posible crear un método para reconstruir el camino real entre los dos vértices de punto final. Aunque uno puede estar inclinado a almacenar el camino real de cada vértice a otro vértice, esto no es necesario, y de hecho, es muy costoso en términos de memoria. En cambio, el árbol más corto-pata puede ser calculado para cada nodo en ${displaystyle Theta (|E|)}$ tiempo utilizando ${displaystyle Theta (|V|)}$ memoria para almacenar cada árbol que nos permite reconstruir eficientemente un camino de cualquier dos vértices conectados.

Pseudocódigo

Deja no ser un  ${displaystyle |V|times |V|}$  array de distancias mínimas inicializadas a  $infty$  (infinito)
Deja prev ser un  ${displaystyle |V|times |V|}$  matriz de índices de vértice inicializados nuloprocedimiento FloydWarshallConPathReconstruction() es para cada uno (u, v) dodist[u][v] ← w(u, v) // El peso del borde (u, v)prev[u][v] ← u
 para cada uno v do← 0
prev[v][v] ← v
 para k desde 1 a Silencio do // estándar Aplicación de Floyd-Warshall para i desde 1 a Silencio
 para j desde 1 a Silencio
 si dist[i][j] √≥ dist[i][k] + dist[k][j] entoncesdist[i][j] ← dist[i][k] + dist[k][j]
prev[i][j] ← prev[k][j]

procedimiento Path(u, v)
 si prev[u][v] = null entonces retorno []
path ← [v]
 mientras u ل vv ← prev[u][v]
path.prepend(v)
 retorno sendero

Análisis de tiempo

Vamos $n$ Ser $|V|$ , el número de vértices. Para encontrar a todos $n^{2}$ de ${displaystyle mathrm {shortestPath} (i,j,k)}$ (para todos) $i$ y $j$ ) de los de ${displaystyle mathrm {shortestPath} (i,j,k-1)}$ Requisitos $2n^{2}$ operaciones. Desde que empezamos con ${displaystyle mathrm {shortestPath} (i,j,0)=mathrm {edgeCost} (i,j)}$ y computar la secuencia de $n$ matrices ${displaystyle mathrm {shortestPath} (i,j,1)}$ , ${displaystyle mathrm {shortestPath} (i,j,2)}$ , $ldots$ , ${displaystyle mathrm {shortestPath} (i,j,n)}$ , el número total de operaciones utilizadas es ${displaystyle ncdot 2n^{2}=2n^{3}}$ . Por lo tanto, la complejidad del algoritmo es $Theta (n^{3})$ .

Aplicaciones y generalizaciones

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

Sendas más cortas en gráficos dirigidos (al algoritmo de Floyd).
Cierre transitorio de gráficos dirigidos (al algoritmo de Warshall). En la formulación original de Warshall del algoritmo, el gráfico no tiene peso y está representado por una matriz de adyacencia booleana. Luego la operación de adición es reemplazada 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 (al algoritmo de Kleene, una generalización estrechamente relacionada con el algoritmo Floyd-Warshall)
Inversión de matrices reales (volumen de Gauss–Jordania)
Oración óptima. 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 minima como en el pseudocódigo anterior, uno toma maxima. Los pesos del borde representan restricciones fijas sobre el flujo. Los pesos del camino representan los cuellos de botella; por lo que la operación de adición anterior es reemplazada por la operación mínima.
Computación rápida de redes Pathfinder.
Senderos más amplios/Máximo ancho de banda
Computing canonical form of difference bound matrices (DBMs)
Computing the similarity between graphs
Cierre transitorio en gráficos AND/OR/threshold.

Implementaciones

Hay implementaciones disponibles para muchos lenguajes de programación.

Para C++, en el impulso:
Para C#, en QuickGraph
Para C#, en QuickGraphPCL (Un tenedor de QuickGraph con mejor compatibilidad con los proyectos utilizando las bibliotecas de clase portátil.)
Para Java, en la biblioteca de Gráficos de 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 (module scipy.sparse.csgraph) o Network X biblioteca
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 computar caminos 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 bordes. Para gráficos escasos con pesos de borde no negativo, la complejidad asintotica más baja se puede obtener ejecutando el algoritmo de Dijkstra de cada posible vértice inicial, desde el peor momento de funcionamiento de Dijkstra repetido ( ${displaystyle O(|E||V|+|V|^{2}log |V|)}$ usando las pilas Fibonacci) es más pequeño que el $O(|V|^{3})$ tiempo de funcionamiento del algoritmo Floyd–Warshall cuando $|E|$ es significativamente menor que $|V|^{2}$ . Para gráficos escasos con bordes negativos pero sin ciclos negativos, el algoritmo de Johnson se puede utilizar, con el mismo tiempo de funcionamiento asintotico que el enfoque repetido de Dijkstra.

También hay 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 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 de Floyd-Warshall para gráficos muy grandes.

Contenido relacionado

Más resultados...