sistemas

 CAMINO MAS CORTO: ALGORITMO DE DIJKSTRA
Publicado el marzo 19, 2012| 4 comentarios
Para el problema de la ruta corta tenemos varios algoritmos, en esta oportunidad se explicará elalgoritmo de dijkstra el cual usa una técnica voraz (greedy). Al final del articulo se encuentran adjuntas las implementaciones en C++ y JAVA.
Descripción
El algoritmo de dijkstra determina la rutamás corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:
Si los pesos de mis aristas son de valor 1,entonces bastará con usar elalgoritmo de BFS.
Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo deBellmand-Ford.
Como trabaja
Primero marcamos 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 dijkstrausa 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ás cerca 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áscercano (con las distancias ya 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 tomandocomo punto intermedio al nuevo vértice se le conoce comorelajación (relaxation).
Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos unaCola 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...