ALGORITMO FLOYD WARSHALL
Marisol Bautista
Lady Cubides
Viviana Tuta
CONTENIDO


DEFINICIÓN

HISTORIA

EJEMPLO
APLICACIONES
HISTORIA
“Por qué esta magnífica tecnología científica, que
ahorra trabajo y nos hace la vida más fácil, nos
aporta tan poca felicidad? La respuesta es ésta:
simplemente porque aún no hemos aprendido a
usarla ” Albert Einstein
ROBERT W. FLOYD
* (8 de junio de 1936 - 25 de septiembre de 2001)
* Floyd culminó bachillerato a los 14 años, Se graduó
en la Universidad de Chicago en 1953 a los 17 años y
como Físico en 1958.
*Operador de computadoras en los años 60.
Publicó sus primeros artículos los cuales fueron de
gran influencia y fue nombrado profesor asociado en
la Universidad de Carnegie Mellon. Seis años más
tarde fue nombrado profesor en la Universidad de
Stanford.
ROBERT W. FLOYD


Entre sus contribuciones se encuentran el diseño y
análisis de algoritmos eficientes para encontrar el
camino más corto en un grafo y para el problema de
reconocimiento de frases, pero probablemente su
logro más importante fue el ser pionero, con su
artículo de 1965 "Assigning Meanings to Programs"",
en el área de verificación de programas utilizando
aserciones lógicas, donde aparece la importante
noción de invariante, esencial para demostrar
propiedades de programas iterativos.
Floyd
recibió
el
Premio
TURING
de
la ACM en 1978 "por tener una clara influencia en las
metodologías para la creación de software eficiente
y confiable, y por haber contribuido a la fundación
de las subáreas teoría del reconocimiento de frases,
semántica de los lenguajes de programación,
verificación automatizada de programas, síntesis
automatizada
de
programas
y
análisis
de
algoritmos."
DEFINICIÓN
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, teniendo en
cuenta que este tipo de programación tiene como
fin encontrar una solución optima a dicho
problema recursivamente.
EJEMPLO
Dado el siguiente grafo:
Llenar la matriz distancia: La diagonal siempre va vacía y el resto de
casillas se llenan de acuerdo a las distancias del grafo:
Matriz Distancia
1
2
3
4
1
-
4
2
5
2
4
-
∞
1
3
2
1
-
2
4
5
1
2
-
Llenar la matriz recorridos: La diagonal siempre va vacía y las demás
casillas se llenan con el mismo número de columna:
Matriz Recorrido
1
2
3
4
1
-
2
3
4
2
1
-
3
4
3
1
2
-
4
4
1
2
3
-

Iteraciones

Eliminar filas y columnas

Se deberán analizar los valores quedan en blanco
(los que no fueron tachados) y la idea es mejorar ese
valor. Esto se hace cuando la suma de componentes
es menor al valor que no está tachado.

Cambiar valores en las matrices

Dibujar matrices finales.

Conclusiones
SOLUCIÓN
Matriz Distancia
Matriz Recorrido
1
2
3
4
1
2
3
4
1
-
3
2
4
1
-
3
3
3
2
4
-
3
1
2
1
-
4
4
3
2
1
-
2
3
1
2
-
4
4
4
1
2
-
4
3
2
3
-
CONCLUSIONES



La distancia entre el punto 1 y 2 es 3. Para llegar es
necesario recorrer los puntos 1-3-2.
La distancia entre el punto 1 y 3 es 2. Para llegar es
necesario recorrer los puntos 1-3.
La distancia entre el punto 1 y 4 es 4. Para llegar es
necesario recorrer los puntos 1-3-4.
APLICACIONES

En el diseño de circuitos.

En el diseño de rutas de transporte.

Aproximaciones al problema del viajante.


Camino mínimo en grafos dirigidos (algoritmo de
Floyd).
Cierre transitivo en grafos dirigidos (algoritmo de
Warshall). Es la formulación original del Algoritmo
de Warshall.



Encontrar una expresión regular dada por un lenguaje
regular aceptado por un autómata finito (algoritmo de
Kleene).
Inversión de matrices de números reales (algoritmo de
Gauss-Jordan).
Ruta optima. En esta aplicación es interesante encontrar
el camino del flujo máximo entre 2 vértices. Esto significa
que en lugar de tomar los mínimos con el pseudocódigo
anterior, se coge el máximo. Los pesos de las aristas
representan las limitaciones del flujo. Los pesos de los
caminos representan cuellos de botella; por ello, la
operación de adición anterior es reemplazada por la
operación mínimo.

Comprobar si un grafo no dirigido es bipartito.

Como base de otros algoritmos más complejos.
REFERENCIAS




Algoritmo de Floyd-Warshall. [En línea]<
http://www.gratisblog.com/warshall/> [Consultado el 20/08/10]
TP:Algoritmo de Warshal - Programación dinámica. [En línea]<
http://156.35.31. 178/wiki/index.php/TP:Algoritmo_de_Warshal__Programaci %C3%B3n_ din%C3 %A1mica> [Consultado el
20/08/10]
Algoritmos de rutas cortas y árboles mst. . [En línea]<
geiser.gcc.googlepages. com/ExposicionAlgoritmoRutasCortas.ppt > [Consultado el 20/08/10]
Algoritmo de Floyd. [En línea]< http://www.cenkui.com/
algoritmodefloyd /algoritmodefloyd.html> [Consultado el
20/08/10]
Descargar

ALGORITMO FLOYD WARSHALL