1 305460135675822115

USB
Carrera: Ingeniería de sistemas
Practica #2
Tema:
Algoritmo de Dijkstra y Niklaus Wirth
Materia:
Algoritmos avanzados
Universitario:
KaelDiego choque cruz
Paralelo:
5 A1
Docente:
Lic. Simón Onofre
Fecha:
07 de abril 2014
Algoritmo de Dijkstra
Hay diferentes algoritmos para hallar uncamino de longitud mínima entre dos vértices de un grafo ponderado. Presentaremos un algoritmo descubierto por el físico holandés Edsger Dijkstra en 1959. La versión que descubriremos resuelve esteproblema para grafos ponderados no dirigidos si todos los pesos no son negativos. Este algorimo puede adaptarse fácilmente para resolver problemas de caminos de longitud mínima en grafo dirigidos.
Primeromarcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy -La técnica greedy utiliza el principio de que para que un camino sea óptimo, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté máscerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distanciasya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio alnuevo vértice se le conoce como relajación (relaxation).
Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos una Cola de Prioridad o Heap,este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los...