Optimizacion Estructural de Grafos. Busqueda de Caminos cortos con el algoritmo Dijkstra

Introducción:
Para esta entrada, eligiéremos una estructura, la modelaremos como un grafo y posteriormente utilizaremos el algoritmo de búsqueda de caminos cortos de  Dijkstra para encontrar la ruta mas corta dado un punto origen a un punto destino.

Justificación:


Dada la intención  de en algún futuro desarrollar un sistema de búsqueda de caminos óptimos a gran escala, que represente datos reales de un determinado lugar como lo puede ser una ciudad, un conjunto de carreteras, etc, se opto por realizar una pequeña implementacion.

Desarrollo:


A continuación mencionaremos las fases en el desarrollo.

Primeramente revisaremos el aspecto teórico.
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

Este consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene .

Nosotros modelamos un grafo con puntos de interés en a Cd. de Monterrey.

El grafo en cuestión es un grafo ponderado no dirigido.

Después transformamos el grafo en su respectiva matriz adyacente.

Esta matriz en cuestión representa los datos del grafo, de esta forma es como podemos computar dichos datos. Aquí representamos los pesos de las aristas como las distancias de un punto a otro,  en caso de no haber un camino directo de un punto a otro, lo podemos marcar con un 0 o con el símbolo de infinito 00

La lógica principal del programa consiste en ir recorriendo cada nodo del grafo y de ahí analizar todas las distancias, de ahí elegimos la mas corta, y guardarla en un arreglo, para posteriormente pasar al siguiente nodo y realizar el mismo proceso. Este algoritmo, simplemente se guía por la búsqueda de un camino con menor peso, sin llegar a considerar otras posibles rutas, que en algunos casos pueden resultar mucho mejores.

El objetivo principal que se tenia previsto era que mediante parámetros especificaríamos los puntos de origen y destino y de ahí se procedería a realizar el proceso, solo que había pequeños detalles, ya que teníamos problemas al elegir determinado nodo, se realizaba el proceso y este volvía a sumar las distancias de los nodos ya procesados. Es por ello que primeramente quisimos implementar algo que me calcule la distancia de un punto a otro y me la imprima, posteriormente implementar algo mas complejo.


Referencias:

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
http://www.youtube.com/watch?v=6rl0ghgPfK0