Algoritmo de Dijkstra

ALGORITMO DE DIJKSTRA PARA RUTAS MÁS CORTAS
(Dijkstra Shortest Paths)

Las gráficas pueden ser usadas para representar muchos tipos de problemas de enrutamiento, como por ejemplo; una gráficapuede representar el sistema de autopistas de un estado de un país, en donde los vértices de la grafica representan a las ciudades y las aristas representan las diferentes secciones de autopista. A lasaristas se les pueden asignar pesos los cuales pueden ser las distancias entre dos ciudades conectadas por una arista, o también puede representar el tiempo de manejo a lo largo de esta sección deautopista. Otro problema que se podría presentar para este ejemplo es el de un motociclista que desea manejar de la ciudad A a la B el cual está interesado en saber si hay un camino entre esas dosciudades y si hay más de un camino, cuál es el más corto.

Estos problemas definidos por estas preguntas son casos especiales de encontrar el camino más corto entre vértices de una gráfica. La longitud deun camino esta ahora definido por la suma de los pesos de las aristas de esos caminos. El vértice de inicio del camino se refiere a cual es el origen, y el último vértice a cual es el destino.
Parael problema que tomaremos tenemos una grafica G = (V,E), una función de peso c(q) para las aristas de G, y un vértice origen vo. El problema consiste en determinar el camino más corto de vo a todoslos vértices restantes en la gráfica G.(Se asume que todos los pesos son positivos).
Para resolver este problema nos basamos en un algoritmo voraz para generar los caminos más cortos; pero debemosconsiderar que hay múltiples soluciones para este problema así como también múltiples optimizaciones. Un solución es construir los caminos más cortos uno por uno. Como una optimización podemos usar lassumas de las distancias de todos los caminos más lejanos generados. Para optimizar lo anterior, cada camino individual debe ser de mínima longitud. Si ya hemos construido i caminos más cortos, después...