Programación dinamia ejercicios

La Corporación Basco S.A.C.  Se dedica a la importación, exportación y distribución de rodamientos, así como insumos de uso minero, cementero, industrial, agroindustrial,siderúrgico, agroquímico, alimentario y metalmecánico. Supóngase que un proveedor de Madrid desea viajar a Praga realizando el viaje en tres etapas. En la primera tieneoportunidad de hospedarse en Marsella, París o Limoges; en la segunda lo hará en Zúrich, Múnich o Milán, para desde ahí trasladarse directamente a Praga. El encargado desea saberdónde debe hospedarse en cada etapa para minimizar el trayecto del viaje. Las distancias en cada etapa son las siguientes:

Marsella
París
Limoges
Madrid
950
1120725


Zurich
Munich
Milan
Marsella
500
700
350
París
430
750
800
Limoges
600
825
570


Praga
Zúrich
Múnich
Milán
625
325
750

Estamos ante unproblema de encontrar el camino más corto en un grafo secuencial (sin circuitos).
SOLUCIÓN
Etapa 3
Se determina la trayectoria más corta a Praga desde cada ciudad donde empiezala tercera etapa:
3+ (Zurich) = 625
3+ (MUnich) = 325
3+ (Milán) = 750

Etapa2
Se determina la trayectoria más corta a Praga desde cada ciudad donde empieza lasegunda etapa:
2+ (Marsella) = Min {500 +3+ (Zúrich), 700 + 3+ (Múnich), 350 + 3+ (Milán)}
= Min {1125, 1025,1100} = 1025 (Marsella-Múnich-Praga)2+ (París) = Min {1055, 1075,1550} = 1055 (París-Zúrich-Praga)
2+ (Limoges) = Min {1225, 1150,1240} = 1150 (Limoges-Múnich-Praga)

Etapa 1
Finalmente, paraestablecer la ruta Optima:
2+ (Madrid) = Min {950 + 2+ (Marsella), 1120 + 2+ (París), 725 + 2+ (Limoges)} = Min {1975, 2175,1875} = 1875 (Madrid-Limoges-Múnich-Praga)