UNIVERSIDAD NACIONAL DEL ALTIPLANO
FACULTAD DE INGENIER IA MECANICA ELECTRICA ELECTRONICA Y SISTEMAS
ESCUELA PROFESIONAL DE INGENIER IA DE SISTEMAS
MONOGRAF IA ALGORITMO DE FLOYD RAUL ROSENDO QUISPE CAYLLAHUA PUNO-PERU 2013
1.
INDICE:
Indice
1. INDICE: 2. DEDICATORIA 3. AGRADECIMIENTOS 4. INTRODUCCION 5. RESUMEN 6. HISTORIA DE FLOYD 6.1. DEFINICIONES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. EJEMPLOS: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7. CONCLUSION 8. BIBLIOGRAF IA 2 3 4 5 6 7 7 8 9 10
2.
DEDICATORIA
Dedicado a mi Madre por el apoyo que me da d a a d a.
3.
AGRADECIMIENTOS
Agradezco a mi madre por darme la oportunidad de estudiar y por haberme motivado a poder culminar este trabajo con exito.
4.
INTRODUCCION
El algoritmo fue ideado por Floyd en 1962 bas andose en un teorema de Warshall . Intenta resolver este algoritmo al encontrar el camino m as corto entre todos los pares de nodos o v ertices de un grafo.
5.
RESUMEN
Algoritmo de programaci on din amica para encontrar los caminos m as Cortos entre todos los pares de v ertices de un grafo dirigido .
6.
HISTORIA DE FLOYD
Robert W. Floyd naci o el 8 de junio de 1936 en Nueva York, es profesor de la Stanford Univercity (B.A. Chicago 1955 B.S. Chicago 1958), y en 1978 fue galardonado con el prestigioso premio A.M. Turing que otorga la ACM para reconocer las contribuciones de naturaleza t ecnica realizadas a la comunidad inform atica. El premio le fue concedido por tener una inuencia clara en las metodolog as para la creaci on de software eciente y able, y por ayudar a fundar las siguientes areas de la inform atica: teor a de an alisis sint actico, sem antica de los leguajes de programaci on, vericaci on autom atica de programas, s ntesis autom atica de programas y an alisis de algoritmos. Fue uno de los inventores del deterministic linear time selecti on algorithm. Tambi en introdujo mejoras en los algoritmos quicksort y quickselect.
6.1.
DEFINICIONES
El problema que intenta resolver este algoritmo es el de encontrar el camino m as corto entre todos los pares de nodos o v ertices de un grafo. Esto es semejante a construir una tabla con todas las distancias m nimas entre pares de ciudades de un mapa, indicando adem as la ruta a seguir para ir de la primera ciudad a la segunda. Este es uno de los problemas m as interesantes que se pueden resolver con algoritmos de grafos.
6.2.
EJEMPLOS:
Camino m nimo entre todos los pares de nodos
Figura 1:
Grafo Dirigido Matriz de Distancia Minima.
0 1 2 3 0 0 8 9 5 1 11 0 1 2 2 11 19 0 16 3 9 3 4 0 4 7 15 6 12
4 7 4 4 2 0
Matriz de Caminos.
0 1 2 3 4
0 4 4 4 4
1 3 3 3 3
2 1 1 1 4
3 0 1 0 0
4 3 3 2 3
7.
CONCLUSION
El algoritmo de Floyd es un an alisis sobre grafos para encontrar el camino m nimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de v ertices en una u nica ejecuci on.
8.
BIBLIOGRAF IA
MICHA ELIAS .M exico Limusa 2003 CONALEP Matematicas Discretas
10
