Ejemplo del problema del camino de mínimo costo

Supongamos que deseamos hallar el camino más corto entre el nodo O hasta el nodo d, donde cada nodo significa una ciudad, la idea es disminuir la distancia recorrida, por lo tanto, es importante seleccionar las ciudades (nodos) por las cuales pasar:

Representación en grafo de las distancias.

(Para ampliar la imagen haga clic sobre ella)

Una manera de resolverlo es realizar una evaluación de las rutas, simplificando el problema así:

Primero podemos encontrar la ruta más corta entre el nodo 1 y el nodo 5. Veamos:

Las rutas pueden ser:

1 - 2 - 5
1 - 3 - 5
1 - 4 - 5

Para evaluar el valor de las rutas es necesario encontrar la ruta más corta, que para el caso del ejemplo equivale a 7 unidades de distancia, equivalente a la ruta 1-4-5, por lo tanto, las dos rutas 1-3-5 y 1-2-5 se descartan:

Representación en grafo de las distancias entre el nodo 1 y 5.

(Para ampliar la imagen haga clic sobre ella)

De igual manera se evalúa la ruta desde el nodo 1 hasta el nodo 6, las rutas son:

1 - 2 - 6
1 - 4 - 6

Es mejor la ruta 1-2-6, por lo tanto, se descarta la ruta 1-4-6, se escoge la ruta 1-2-6 debido a que la sumatoria de la distancia de la ruta son 6 unidades de distancia, y la ruta 1-4-6 son de 11, (2+9):

Representación en grafo de las distancias entre el nodo 1 y 6.

(Para ampliar la imagen haga clic sobre ella)

Hemos hallado la ruta óptima hasta V3, es decir que nos encontramos en los nodos 5 y se hace necesario evaluar cuál ruta tomar:

Representación en nodo de la distancia entre el nodo 5 y 6 al nodo 10.

(Para ampliar la imagen haga clic sobre ella)

Debemos evaluar la ruta entre 5–10 y 6-10, las rutas entre 5–10 son:

5 - 7 - 10
5 - 8 - 10
5 - 9 - 12

Representación en grafo de las distancias entre el nodo 5 al nodo y 10.

(Para ampliar la imagen haga clic sobre ella)

La mejor ruta entre 5 y 10 es 5-7-10, debido a que su unidad de distancia es menor, 13, (8+5).

La ruta 5-8-10, la distancia es 20 (11+9), una distancia mayor, por lo tanto, se descarta esta ruta.

De igual modo se evalúa la distancia entre 6 y 10, siendo la ruta 6-8-10.

Representación en grafo de las distancias entre el nodo 6, al nodo 10.

(Para ampliar la imagen haga clic sobre ella)

Por lo tanto, se ha resuelto el ejercicio, donde la ruta óptima mínima es 1-2-6-8-10.

Representación en grafo de las distancias 1 y nodo 10, solución del ejercicio

(Para ampliar la imagen haga clic sobre ella)