jueves, 21 de octubre de 2010

CLASE - Selección e Iteración

Lenguajes de Programación - Semana 11 - Tarea 9 - Tercera Presentación

ALGORITMO DE FLOYD-WARSHALL

Diapositiva 1



Diapositiva 2


Ideado por Robert W. Floyd en 1962 basado en el Teorema de Warshall, es un algoritmo de análisis y optimizacion. Su objetivo encontrar la distancia mínima entre los vertices que forman un grafo, los cuales pueden tener una direccion y una ponderacion.

Diapositiva 3


Tenemos un grafo G con n vertices V y queremos ir por el Camino C, osea, ir del vertice 1 al 4. Sabemos que podemos pasar por puntos intermedios K que iran desde V1+1 a Vn-1. El algoritmo comparara todos los posibles caminos entre el par de vértices, teniendo un posible punto intermedio y se hara la estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es la óptima.
Este es el pseudocodigo lo explicare al grandes razgos la parte verde indica la carga de los datos, la funcion floyd_warshall, recibe el numero de vertices y una matriz cuadrada W de n X n vertices, se crea la matriz principal de distancias y una matriz de pasos, despues con los cliclos for de va cargando uno a uno los datos de W a D.
La parte roja son los ciclos principales del algoritmo, ahi se van comparando las distancias del vertice i al j pasando por k. Se comparan la suma de las coordenadas de las componentes de la matriz, si la suma es menor a la distancia original se mejora y se marca el paso en la matriz pasos y al terminar se regresa la matriz D optimizada
El algoritmo realiza V^3 comparaciones, es decir, aqui se pueden realizar hasta 64 comparaciones!!!

Diapositiva 4: Resultados Animación


Diapositiva 5: Referencias



Descarga: presentacion.odp

Descarga animación: Presentacion.mpeg

Saludos!! ^_^

1 comentario:

  1. Que bien que explicas tus diapositivas. Te pongo dos puntos extra en la clase.

    ResponderEliminar