The Stagecoach Problem A mythical salesman who had to travel west by stagecoach, through unfriendly country, wished to take the safest route. His starting point and destination were fixed, but he had considerable choice as to which states he would travel through en route. The possible stagecoach routes are shown in Figure 1.
After some thought, the salesman deduced a clever way of determining his safest route. Life insurance policies were offered to passengers, and since the cost of each policy was based on a careful evaluation of the safety of that run, the safest route should be the one with the cheapest policy.
The cost of the standard policy on the stagecoach run from state i to state j, denoted as Cij, is given in Figure 2. Find the safest path(s) for the salesman to take.
