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!! ^_^
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!! ^_^
Que bien que explicas tus diapositivas. Te pongo dos puntos extra en la clase.
ResponderEliminar