Algoritmo De Floyd-Warshall
El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V^3 comparaciones (esto es notable considerando que puede haber hasta V^2 aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.
Algoritmo:
Dado un grafo G(V,A) se puede aplicar el algoritmo de Floyd para resolver el problema de encontrar el camino más corto de todos los vértices entre sí.
Inicio
Armar la matriz de adyacencia F, teniendo en cuenta que F(i,j)=0 si i = j (diagonal principal es 0). Además dónde no exista camino se debe indicar con infinito.
Para k desde 1 hasta n
Para i desde 1 hasta n
Para j desde 1 hasta n
F[i,j]=min(F[i,j], F[i,k] + F[k,j])
Fin para j
Fin para i
Fin para k
En la k-esima vuelta F[i, j] contendrá el valor del camino más corto que una al vértice i con el j tal que dicho camino no pase por un vértice con número mayor que k.
La matriz resultante es la de los mínimos caminos entre cada nodo. Si se quiere saber cual es dicho camino, se debe armar un árbol a medida tomando como numero de nodo a k cada vez que se detecta que hubo una optimización.
Debido a su triple ciclo anidado es obviamente O(N^3).
imagen :
Ejemplo : En esta pagina no tiene lucros con este vídeo
Dado un grafo G(V,A) se puede aplicar el algoritmo de Floyd para resolver el problema de encontrar el camino más corto de todos los vértices entre sí.
Inicio
Armar la matriz de adyacencia F, teniendo en cuenta que F(i,j)=0 si i = j (diagonal principal es 0). Además dónde no exista camino se debe indicar con infinito.
Para k desde 1 hasta n
Para i desde 1 hasta n
Para j desde 1 hasta n
F[i,j]=min(F[i,j], F[i,k] + F[k,j])
Fin para j
Fin para i
Fin para k
En la k-esima vuelta F[i, j] contendrá el valor del camino más corto que una al vértice i con el j tal que dicho camino no pase por un vértice con número mayor que k.
La matriz resultante es la de los mínimos caminos entre cada nodo. Si se quiere saber cual es dicho camino, se debe armar un árbol a medida tomando como numero de nodo a k cada vez que se detecta que hubo una optimización.
Debido a su triple ciclo anidado es obviamente O(N^3).
imagen :
Ejemplo : En esta pagina no tiene lucros con este vídeo
Para mayor información sigueme en:
CIBERGRAFIA
No hay comentarios:
Publicar un comentario