Nanotecnologias

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áfica puede 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 de autopista. 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 dos ciudadesy 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 de un 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 todos los 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 las sumas 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ésusamos esta optimización, en próximo camino a ser construido debe ser el próximo camino con longitud más corta. Esta forma voraz de generar los caminos más cortos de vo a el resto de todos los vértices de una grafica es
para generar estos caminos en orden no-decreciente. Primero, generamos en camino más corto al vértice más cercano del origen. Después se genera el camino más corto al segundovértice mas cercano, y así sucesivamente. En el problema y en el algoritmo la S denota un grupo de vértices (incluyendo a vo) para los cuales los caminos mas cortos ya fueron generados. Para una w que no esta en S, dist(w) es la longitud del camino mas corto de vo, yendo solo desde estos vértices que estan en el conjunto S, y terminan en w. Pero debemos tener en cuenta lo siguiente:

- Si el caminomas corto es para un vértice u, después el camino empieza en vo, y termina en una u, estos deben de ser solo de los vértices que estan en S. Para lograr esto, debemos mostrar que todos los vértices intermedios en el camino más corto a u, estan en S. Asumimos que este es un vértice w en este camino que no esta en S. Después, el camino de vo a u, tambien contiene un camino de vo a w el cual tiene unalongitud menor que el camino de vo a u.

- El destino del siguiente camino generado debe de estar en el vértice u, el cual tiene la minima distancia, dist(u), de entre todos los vértices que no estan en S.

- habiendo seleccionado un vértice u con la observación anterior y generado el camino mas corto de vo a u, el vértice u se convierte en un miembro de S. En este punto la longitud delcamino mas corto empieza en vo, yendo solo hacia los vértices que estan en S y terminando en un vértice w que no esta en S que puede decrementarse, entonces el valor de su distancia dist(w) puede cambiar. Si cambia, entonces este debe ser debido a que el camino mas corto empieza en vo y va a u y después a w.

Los vértices intermediarios en vo a u y el camino de u a w deben todos estar en S....