1. The table shows the least distances, in km, between five hiding places, A, B, C, D and E.
Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A , and wishes to minimise the total distance travelled.

1. Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
2. Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
3. Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
4. State the better upper bound from your answers to (b) and (c).
5. Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
6. Consider your answers to (d) and (e) and hence state an optimal route.