Algoritmo de Floyd Warshall
Queremos determinar los caminos más cortos entre todos los pares de vértices. Podríamos usar Dijkstra de botones vado, con cada vértice como fuente. ¿Podemos hacerlo mejor? En el algoritmo de Floyd Warshall, asumimos que tenemos acceso a un grafico con n vértices como matriz de adyacencia n².
El algoritmo de Floyd Warshall toma como entrada un gráfico dirigido y valorado, descrito por una matriz de adyacencia que da el peso de un arco cuando existe y el valor ∞ en caso contrario. El peso de un camino entre dos vértices es la suma de los pesos en los arcos que constituyen este camino. Los arcos del gráfico pueden tener pesos negativos, pero el gráfico no debe tener un circuito de peso estrictamente negativo. El algoritmo calcula, para cada par de vértices, el peso mínimo entre todos los caminos entre estos dos vértices.
Condiciones.
- Caso general extendido
Suponemos que los vértices de G son {1, 2, 3, 4, ..., no}. Resuelve sucesivamente los siguientes subproblemas:
Wkij es el peso mínimo de un camino desde el vértice i al vértice j tomando prestados solo vértices intermedios en {1, 2, 3,…, k} si hay uno, y ∞ en caso contrario. Denotamos por Wk la matriz de Wkij.
Para k = 0, W0 es la matriz de adyacencia que define el gráfico.
Para encontrar una relación de recurrencia, consideramos un camino pag Entre I y j de peso mínimo cuyos vértices intermedios están en {1, 2, 3,…, k} :
- es decir pag no tomes la cumbre k
- es decir pag toma prestado exactamente una vez que la cumbre k y pag es, por tanto, la concatenación de dos caminos, entre I y k y k y j respectivamente, cuyos vértices intermedios están en {1, 2, 3,…, k-1}.
Sea p el camino más corto de i a j con todos los vértices intermedios del conjunto {1,. . . , k}. Si k no es un vértice intermedio de p, entonces p también es un camino más corto con todos los vértices intermedios del conjunto {1,. . . , k - 1}. Si k es un vértice intermedio de p, descomponemos p en un camino p1 entre i y k, y un camino p2 entre k y j; estos son los caminos más cortos.
La observación anterior da la relación de recurrencia:
Wkij= min (Wk-1ij, Wk-1ik + Wk-1K J ), para todos I, j y k en {1, 2, 3, 4…, no}.
Por tanto, resolvemos los subproblemas aumentando el valor de k.
Lo que da en las dos primeras etapas:
Ejemplo del algoritmo de Floyd Warshall
La primera matriz es la matriz adyacente y luego los caminos más cortos. La segunda matriz presenta a los predecesores. Se inicializa con un valor z que es igual al número de la fila si existe un valor en la matriz de adyacencia (en el estado inicial). La matriz de predecesores se actualiza cada vez que se modifica un valor en (i, j). El valor correspondiente en (i, j) de la matriz de los predecesores es igual al número de iteraciones (es decir, el valor de la potencia de la matriz).
Optimidad del algoritmo Floyd Warshall
Inicialmente, tenemos los senderos de tamaño 1 más cortos que comienzan desde todos los picos. A continuación, calculamos las rutas de mayor tamaño a través del vértice 1 y mantenemos solo las rutas más cortas. Por lo tanto, la nueva iteración muestra las rutas más cortas de tamaño 1 y las de tamaño 2 que pasan por el vértice 1. Por inducción, deducimos que la última matriz muestra las rutas más cortas de tamaño menor que el número de vértices entre cualquier par de vértices.
CODE W es la matriz de adyacencia
para k de 1 an
para yo de 1 a n
para j de 1 an Wkij= min (Wk-1ij, Wk-1ik + Wk-1K J )
fin
fin
fin
volver W
ES 
FR 
EN