LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

 el algoritmo de Floyd-Warshall(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 encontrar el camino más corto en un grafo ponderado con pesos de las aristas positivas o negativas (pero sin ciclos negativos). ^[1] [2]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 usar para encontrar el cierre transitivo de una relación$${\ displaystyle R}, 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.

Algoritmo Floyd – Warshall

Clase	El problema de la ruta más corta de todos los pares (para los gráficos ponderados)
Estructura de datos	Grafico
Peor desempeño	$${\ displaystyle \ Theta (| V | ^ {3})}
El mejor rendimiento del caso	$${\ displaystyle \ Theta (| V | ^ {3})}
Rendimiento medio	$${\ displaystyle \ Theta (| V | ^ {3})}
La peor complejidad del espacio	$${\ displaystyle \ Theta (| V | ^ {2})}

Historia y denominación [ editar ]

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 previamente publicados por Bernard Roy en 1959 ^[4] y también por Stephen Warshall en 1962 ^[5] para encontrar el cierre transitivo de una gráfica, ^[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 forados anidados fue descrita por primera vez por Peter Ingerman, también en 1962. ^[8]

Algoritmo [ editar ]

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

Considera una gráfica $${\ displaystyle G} con vértices $${\ displaystyle V} numerado del 1 al $${\ displaystyle N}. Considere además una función$${\ displaystyle \ mathrm {shortestPath} (i, j, k)} que devuelve el camino más corto posible desde $${\ displaystyle i} a $${\ displaystyle j} usando vértices solo del conjunto $${\ displaystyle \ {1,2, \ ldots, k \}}Como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino más corto de cada$${\ displaystyle i} a cada $${\ displaystyle j} usando solo vértices en $${\ displaystyle \ {1,2, \ ldots, N \}}.

Para cada uno de estos pares de vértices, la $${\ displaystyle \ mathrm {shortestPath} (i, j, k)} podría ser cualquiera

(1) Un camino que no pasa. $${\ displaystyle k} (Solo usa vértices en el conjunto. $${\ displaystyle \ {1, \ ldots, k-1 \}}.)

o

(2) un camino que pasa por $${\ displaystyle k} (desde $${\ displaystyle i} a $${\ displaystyle k} y luego desde $${\ displaystyle k} a $${\ displaystyle j}, ambos solo usando vértices intermedios en $${\ displaystyle \ {1, \ ldots, k-1 \}})

Sabemos que el mejor camino desde $${\ displaystyle i} a $${\ displaystyle j} que solo usa vértices $${\ displaystyle 1} mediante $${\ displaystyle k-1} es definido por $${\ displaystyle \ mathrm {shortestPath} (i, j, k-1)}, y está claro que si hubiera un mejor camino desde $${\ displaystyle i} a $${\ displaystyle k} a $${\ displaystyle j}, entonces la longitud de este camino sería la concatenación del camino más corto desde $${\ displaystyle i} a $${\ displaystyle k} (Sólo usando vértices intermedios en $${\ displaystyle \ {1, \ ldots, k-1 \}}) y el camino más corto desde $${\ displaystyle k} a $${\ displaystyle j} (Sólo usando vértices intermedios en $${\ displaystyle \ {1, \ ldots, k-1 \}}).

Si $${\ displaystyle w (i, j)} es el peso del borde entre vértices $${\ displaystyle i} y $${\ displaystyle j}, podemos definir $${\ displaystyle \ mathrm {shortestPath} (i, j, k)}en términos de la siguiente fórmula recursiva : el caso base es

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

y el caso recursivo es

$${\ 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)}}.

Esta fórmula es el corazón del algoritmo Floyd – Warshall. El algoritmo funciona por primera computación.$${\ displaystyle \ mathrm {shortestPath} (i, j, k)} para todos $${\ displaystyle (i, j)} pares para $${\ displaystyle k = 1}, entonces $${\ displaystyle k = 2}, y así. Este proceso continúa hasta$${\ displaystyle k = N}, y hemos encontrado el camino más corto para todos. $${\ displaystyle (i, j)}pares utilizando cualquier vértice intermedio. El pseudocódigo para esta versión básica es el siguiente: ^{[ investigación original? ]}

1 sea dist | a | V | × | V | matriz de distancias mínimas inicializadas a ∞ (infinito)
2 para cada borde ( u , v )
3 dist [ u ] [ v ] ← w ( u , v )   // el peso del borde ( u , v ) 
4 para cada vértice v 
5 dist [ v ] [ v ] ← 0
6 para  k  de 1 a | V |
7     para  i  desde 1 hasta | V |
8        para  j  de 1 a | V |
9           si dist [ i ] [ j ]> dist [ i ] [ k ] + dist [ k ] [ j ]
10 dist [ i ] [ j ] ← dist [ i ] [ k ] + dist [ k ] [ j ]Final 
11          si

Ejemplo [ editar ]

El algoritmo anterior se ejecuta en el gráfico a la izquierda a continuación:

Antes de la primera recursión del bucle externo, etiquetado k = 0 arriba, las únicas rutas conocidas corresponden a los bordes individuales en el gráfico. En k = 1 , se encuentran las rutas que atraviesan el vértice 1: en particular, se encuentra la ruta [2,1,3], reemplazando la ruta [2,3] que tiene menos bordes pero es más larga (en términos de peso) ). En k = 2 , se encuentran las rutas 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, se encuentran caminos que atraviesan los vértices {1,2,3}. Finalmente, en k = 4 , se encuentran todos los caminos más cortos.

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

k = 0		j
		1	2	3	4
yo	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 1		j
		1	2	3	4
yo	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 2		j
		1	2	3	4
yo	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0

k = 3		j
		1	2	3	4
yo	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0

k = 4		j
		1	2	3	4
yo	1	0	−1	−2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	−1	1	0

Comportamiento con ciclos negativos [ editar ]

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

• El algoritmo Floyd-Warshall revisa iterativamente las longitudes de ruta entre todos los pares de vértices $${\ displaystyle (i, j)}incluyendo donde $${\ displaystyle i = j};
• Inicialmente, la longitud del camino. $${\ displaystyle (i, i)} es cero;
• Un camino $${\ displaystyle [i, k, \ ldots, i]} solo puede mejorar esto si tiene una longitud menor que cero, es decir, denota un ciclo negativo;
• Así, después del algoritmo, $${\ displaystyle (i, i)} será negativo si existe un camino de longitud negativa desde $${\ displaystyle i} de regreso $${\ displaystyle 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 la gráfica contiene al menos un ciclo negativo. ^[9] Para evitar problemas numéricos, se deben verificar los números negativos en la diagonal de la matriz de trayectoria dentro del bucle interno para el algoritmo. ^[10] Obviamente, en una gráfica no dirigida, un borde negativo crea un ciclo negativo (es decir, una caminata cerrada) que involucra sus vértices incidentes. Teniendo en cuenta todos los bordes de los anteriores. ejemplo del gráfico no están dirigidos, por ejemplo, la secuencia de vértice 4 - 2 - 4 es un ciclo con una suma de pesos -2.

La reconstrucción ruta [ editar ]

El algoritmo Floyd-Warshall generalmente 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 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, el árbol de la ruta más corta se puede calcular para cada nodo en$${\ displaystyle \ Theta (| E |)} tiempo usando $${\ displaystyle \ Theta (| V |)} memoria para almacenar cada árbol, lo que nos permite reconstruir de manera eficiente una ruta desde dos vértices conectados.

Pseudocódigo ^[11] [ editar ]

que dist sea un$${\ displaystyle | V | \ times | V |}
  
 matriz de distancias mínimas inicializadas a $${\ displaystyle \ infty}
  
(infinito)
 deja que la próxima sea una$${\ displaystyle | V | \ times | V |}
  
matriz de índices de vértices inicializados a nulo

procedimiento  FloydWarshallWithPathReconstruction ()
    para cada borde (u, v)
      dist [u] [v] ← w (u, v)   // el peso del borde (u, v)
      siguiente [u] [v] ← v
   para cada vértice v
      dist [ v ] [ v ] ← 0
      siguiente [v] [v] ← v
   para k de 1 a | V | // 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]
               siguiente [i] [j] ← siguiente [i] [k]

procedimiento Ruta (u, v)
    si siguiente [u] [v] = nulo entonces
        devuelva []
   ruta = [u]
   mientras u ≠ v
       u ← siguiente [u] [v]
       path.append (u)
   ruta de
 retorno

Análisis [ editar ]

Dejar $${\ displaystyle n} ser $${\ displaystyle | V |}, el número de vértices. Para encontrar todo$${\ displaystyle n ^ {2}} de $${\ displaystyle \ mathrm {shortestPath} (i, j, k)} (para todos $${\ displaystyle i} y $${\ displaystyle j}) de los de $${\ displaystyle \ mathrm {shortestPath} (i, j, k-1)} requiere $${\ displaystyle 2n ^ {2}}operaciones Como empezamos 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)}, el número total de operaciones utilizadas es $${\ displaystyle n \ cdot 2n ^ {2} = 2n ^ {3}}. Por lo tanto, la complejidad del algoritmo es$${\ displaystyle \ Theta (n ^ {3})}.

Aplicaciones y generalizaciones [ editar ]

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

• Rutas más cortas en gráficos dirigidos (algoritmo de Floyd).
• Cierre transitivo de gráficos 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 adición se reemplaza por la conjunción lógica (AND) y la operación mínima por disyunción lógica (OR).
• Encontrar una expresión regular que denote el lenguaje regular aceptado por un autómata finito ( el 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, uno está interesado en 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, uno toma máximos. Los pesos de borde representan restricciones fijas en el flujo. Los pesos de las rutas 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 las redes de Pathfinder .
• Rutas más anchas / Rutas de ancho de banda máximo
• Cálculo de la forma canónica de matrices unidas por diferencias (DBMs)
• Cálculo de la similitud entre gráficos.

Implementaciones [ editar ]

Las implementaciones están disponibles para muchos lenguajes de programación .

• Para C ++ , en la librería boost :: graph
• Para C # , en QuickGraph
• Para C # , en QuickGraphPCL (una bifurcación de QuickGraph con mejor compatibilidad con los proyectos que utilizan las bibliotecas de clases portátiles).
• Para Java , en la biblioteca de Apache Commons Graph
• Para JavaScript , en la biblioteca de 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 los paquetes e1071 y Rfast.

Comparación con otros algoritmos de ruta más corta [ editar ]

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 bordes. Para gráficos dispersos con pesos de bordes no negativos, una mejor opción es usar el algoritmo de Dijkstra de cada vértice de inicio posible, ya que el tiempo de ejecución de Dijkstra repetido ($${\ displaystyle O (| E || V | + | V | ^ {2} \ log | V |)}utilizar montones de Fibonacci ) es mejor que el$${\ displaystyle O (| V | ^ {3})} tiempo de ejecución del algoritmo Floyd – Warshall cuando $${\ displaystyle | E |} es significativamente más pequeño que $${\ displaystyle | V | ^ {2}}. 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 de Dijkstra repetido.

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 borde (como la necesidad de que sean enteros pequeños). ^[14] [15] 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.