CAsos GrafosIOIII

Casos de Ruta Mas Corta
Una Cía. Dedicada al alquiler o renta de autos esta evaluando un reemplazo de su flota de autos
para las próximos cinco años. Un automóvil debe estar en servicio como mínimoun año, para
luego considerar su reemplazo. La siguiente tabla muestra el resumen de los costos de reemplazo
(en miles de dólares) en función del número de años en operación. Los costos incluyen elmonto
de compra, el seguro, operación y mantenimiento.
1

2

1
2
3
4

3
5,4
4,3

4

4
9,8
6,2
4,8

5
13,7
8,1
7,1
4,9

Con esta información cada cuantos años deben ser reemplazados y el año máximo de suvigencia
de su flota de automóviles
Solución: El grafo que representa el caso dado es:
13.7
9.8
5.4
4.9

4.8
1

2

4

3

4.3

4

5

6.2
8.1

7.1

Nota: Aplicar el algoritmo de Dijkstra para encontrarla solución del caso.
Caso 2: La Ruta Mas Confiable.
Una Ejecutiva debe conducir todos los días de su casa hacia su trabajo. Como ella sabe de teoría
de grafos, ha determinado la ruta mas corta parallegar a su trabajo. Desafortunadamente esta ruta
mas corta tiene un control policial muy estricto (sobre todo en las horas punta), que le ha
ocasionado fuertes pagos de multas por sobrepasarse loslímites de velocidad. Debido a ello es
claro que la ruta mas corta no es una buena opción para ella. La ejecutiva ha decidido buscar una
nueva ruta que maximice la probabilidad que no sea detenida por lapolicía, para ello analiza el
grafo (la red) con las posibles rutas factibles en función de las estimaciones de probabilidad que
ella asigno para cada ruta, tal como muestra el siguiente grafo. Cualserá la ruta mas confiable
desde su casa (nodo 1) hasta su trabajo (nodo 7).
0.35

0.8
2

4

6

0.2

0.5
0.6
0.1

1

0.4
7

0.9
0.25
3

0.3

5

Solución: El algoritmo del camino mas corto no se puedeaplicar de modo directo, pues las
cantidades asignadas a los arcos del grafo son probabilidades; por lo que se debe aplicar un
artificio. Tomar logaritmos y luego aplicar el algoritmo y al resultado...