Camino Mas Corto

El Problema del Camino más Corto

El problema es determinar la mejor manera de cruzar una red para encontrar la forma más económica posible desde un origen a un destino dado. Suponga que en una red dada existen m nodos y n arcos (bordes) y un costo Cij asociado con cada arco (i a j) en la red. Formalmente, el problema del camino mas corto (CC) es encontrar el camino mas corto (menor costo) desde el nodo de comienzo 1 hasta el nodo final m. El costo del camino es la suma de los costos de cada arco recorrido. Defina las variables binarias Xij, donde Xij =1 si el arco (i a j) es sobre el CC y Xij = 0 de lo contrario. Existen dos nodos especiales llamados origen y destino. El objetivo es encontrar el camino mas corto entre el origen y el destino.

El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino.

Se trata de encontrar la ruta de menor distancia, o costo, a entre el punto de partida o nodo inicial y el destino o nodo terminal.

 -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.

 -Arcos bi-direccionales conectan los nodos con distancias mayores que cero.

 -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.

 Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino.

Pasos a seguir

1. Elaborar un cuadro con todos los nodos y los ramales que salen de él.

2. Partiendo del origen, debemos encontrar el nodo más cercano a él.

3. Anular todos los ramales que entren al nodo más cercano elegido.

4. Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino

...