Algoritmos Floyd Warshall

UNIVERSIDAD TÉCNICA ESTATAL DE QUEVEDO
UNIDAD DE ADMISIÓN Y REGISTRO
NOMBRE:
JENNIFER ESTEFANIA DELGADO BRAVO.
ASIGNATURA:
ALGORITMOS
PARALELO:
FCI1ATELEMATICA-NIVELACION
NOMBRE DEL DOCENTE:
FREDDY CHAMORRO PALACIOS
PERIODO:
2S_2018
Algoritmo de Floyd-Warshall
 En informática, el algoritmo de Floyd-Warshall, descrito en
1959 por Bernard Roy, es un algoritmo de análisis sobre grafos
para encontrar el camino mínimo en grafos dirigidos
ponderados. El algoritmo encuentra el camino entre todos los
pares de vértices en una única ejecución. El algoritmo de Floyd-
Warshall es un ejemplo de programación dinámica.
 Muchos problemas de la vida cotidiana se pueden expresar e
incluso resolver en forma de grafo. Existen algoritmos que
encuentran distintos tipos de soluciones, tanto booleanas como
de eficiencia. El grafo se representa en una tabla (matriz) que
se conoce como “matriz de adyacencia” y representa si existe
una unión entre dos nodos (boolean).
El algoritmo de Floyd
 El algoritmo de Floyd es muy similar, pero trabaja con grafos ponderados. Es decir, el valor de la “flecha” que
representamos en la matriz puede ser cualquier entero o infinito. Infinito marca que no existe unión entre los
nodos. Esta vez, el resultado será una matriz donde estarán representadas las distancias mínimas entre nodos,
seleccionando los caminos más convenientes según su ponderación (“peso”). Por ejemplo, si de “A” a “B” hay 36
(km), pero de “A” a “C” hay 2(km) y de “C” a “B” hay 10 (km), el algoritmo nos devolverá finalmente que de “A”
a “B” hay 12 (km).
 Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes:
 * Formar las matrices iniciales C y D.
 * Se toma k=1.
 * Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i≠k, j≠k e i≠j, hacemos:
 Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj
 En caso contrario, dejamos las matrices como están.
 * Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario páramos las interacciones.
 * La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los
penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino
óptimo para ir de un vértice a otro.
Algoritmo de Floyd - Warshall
 Sea G un grafo con m nodos, u 1, u 2,..., u m suponga que queremos
encontrar la matriz de caminos P para el grafo G. WARSHALL dio un algoritmo
para este propósito que es mucho más eficiente que calcular las potencias de
la matriz de adyacencia A y aplicar la proposición: donde sea A la matriz de
adyacencia y P = Pij la matriz de caminos de un grafo G entonces, Pij = 1 si y
solo sí hay un número positivo en la entrada ij de la matriz.
 El algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un

algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos
dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares
de vértices en una única ejecución.
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í.
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 cuál 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).
Ejemplo:
Matriz de Distancias mínimas:
N1\N2 0 1 2 3 4
0 0 8 9 5 7
1 11 0 1 2 4
2 11 19 0 16 4
3 9 3 4 0 2
4 7 15 6 12 0
Matriz de Caminos:
N1\N2 0 1 2 3 4
0 - 3 1 0 3
1 4 - 1 1 3
2 4 3 - 0 2
3 4 3 1 - 3
4 4 3 4 0 -
Listado de Caminos:
0 --(0)--> 0 = 3 --(4)--> 2 = 3, 1, 2
0 --(8)--> 1 = 0, 3, 1 3 --(0)--> 3 =
0 --(9)--> 2 = 0, 3, 1, 2 3 --(2)--> 4 = 3, 4
0 --(5)--> 3 = 0, 3 4 --(7)--> 0 = 4, 0
0 --(7)--> 4 = 0, 3, 4 4 --(15)--> 1 = 4, 0, 3, 1
1 --(11)--> 0 = 1, 3, 4, 0 4 --(6)--> 2 = 4, 2
1 --(0)--> 1 = 4 --(12)--> 3 = 4, 0, 3
1 --(1)--> 2 = 1, 2 4 --(0)--> 4 =
1 --(2)--> 3 = 1, 3
1 --(4)--> 4 = 1, 3, 4
2 --(11)--> 0 = 2, 4, 0
2 --(19)--> 1 = 2, 4, 0, 3, 1
2 --(0)--> 2 =
2 --(16)--> 3 = 2, 4, 0, 3
2 --(4)--> 4 = 2, 4
3 --(9)--> 0 = 3, 4, 0
3 --(3)--> 1 = 3, 1

Algoritmos Floyd Warshall

Cargado por

Copyright:

Formatos disponibles

Algoritmos Floyd Warshall

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Algoritmos Floyd Warshall

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD TÉCNICA ESTATAL DE QUEVEDO

UNIDAD DE ADMISIÓN Y REGISTRO

 El algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un

También podría gustarte