Problema de la ruta mas corta

Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino (Hillier, 2010).

La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino (Hillier, 2010).

▸Determine la ruta más corta en millas, para el ejemplo de Seervada Park.

▸PASO 1. Iniciar desde el nodo de origen e ir avanzando hacia el nodo final (recursividad de avance).

▸PASO  2. Colocar entre corchetes en el lado izquierdo el valor que tiene la rama y en el lado derecho la letra o numero correspondiente al nodo predecesor.

▸PASO 3. Seleccionar el corchete con el valor menor y continuar hacia adelante a partir de este.

▸NOTA 1: Cuando se selecciona un nuevo nodo con el valor menor, se debe ir contemplando la suma acumulativa de las ramas anteriores correspondientes.

SOLUCIÓN DEL EJEMPLO PROTOTÍPICO POR ALGORITMO DE DIJKSTRA

▸Se selecciona el nodo A puesto que tiene la distancia más corta de los 3 nodos que salen del origen.

▸Continuando a partir del nodo A, se busca a que nodos se conecta y se suma el valor de la rama anterior más el valor de la rama actual y se elige el menor, en este caso es el nodo B.

▸Se descarta el nodo B, puesto que no mejora la distancia del nodo origen al nodo C, al contrario aumenta, y se selecciona el nodo E.

▸Se selecciona el nodo D, sin embargo, hay dos opciones que llevan al nodo D con el mismo valor, por lo cual se consideran dos alternativas.

▸Finalmente se llega al nodo final con un valor de 13 millas que representa la distancia más corta, siendo la ruta más corta las mostradas en rojo y azul.

Conclusión

▸La distancia más corta desde la entrada del parque hasta el mirador es de 13 millas, las dos rutas óptimas (trayectorias) son las siguientes:

▸O-A-B-E-D-T

▸O-A-B-D-T

▸Esta ruta permite reducir costos de transportación de los vehículos que llevan a los visitantes, por ejemplo costos de gasolina.