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 de 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 hasta el vértice j usando solo vértices intermedios en {1, 2, 3, …, k} si lo hay, y ∞ en caso contrario. Notamos Wk la matriz de Wkij.
Para k = 0, W0 es la matriz de adyacencia que define el grafo.
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 parte superior 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 un 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 es también 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 iyk, y un camino p2 entre kyj; 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 de los caminos adyacentes y luego los más cortos. La segunda matriz presenta los predecesores. Se inicializa con un valor z que es igual al número de fila si existe un valor en la matriz de adyacencia (en el estado inicial). La matriz predecesora se actualiza cada vez que cambia un valor en (i, j). El valor correspondiente en (i, j) de la matriz de predecesores es igual al número de iteraciones (es decir, el valor de la potencia de la matriz).
Optimalidad del algoritmo de 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
