The figure that follows shows the trails of Littleville’s Memorial Park.

Whenever there is a major event there, heavy hot dog and soft-drink carts are stored in the shed and rolled out along the trails to the five marked locations.
Numbers on trail links indicate their length, and arrows show which way is uphill. The work to push a cart uphill on any link is proportional to that length. Carts can also be moved in the opposite direction, but the downhill effort is only half as much.

(a) Show how the problem of finding the least total-effort-push routes for all carts can be modeled as a shortest path problem. Also sketch the corresponding digraph, and label it with arc lengths.

(b) Is your digraph acyclic? Explain.

(c) Determine which of the algorithms of this chapter would solve your shortest path problem most efficiently, and justify your choice.

(d) Apply your chosen algorithm to compute optimal move routes.

Transcribed Image Text:

shed #1 10 20 16 #2 20 10 14 #5 18 20 #4 12 #3 38