3. The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H.
| A | B | C | D | E | F | G | H |
| A | - | 36 | 38 | 40 | 23 | 39 | 38 | 35 |
| B | 36 | - | 35 | 36 | 35 | 34 | 41 | 38 |
| C | 38 | 35 | - | 39 | 25 | 32 | 40 | 40 |
| D | 40 | 36 | 39 | - | 37 | 37 | 26 | 33 |
| E | 23 | 35 | 25 | 37 | - | 42 | 24 | 43 |
| F | 39 | 34 | 32 | 37 | 42 | - | 45 | 38 |
| G | 38 | 41 | 40 | 26 | 24 | 45 | - | 40 |
| H | 35 | 38 | 40 | 33 | 43 | 38 | 40 | - |
Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.
- Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.
- State the weight of the minimum spanning tree.
- Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy’s route.
- Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.
- State the best upper bound that can be obtained by using your answers to (c) and (d).
- Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy’s route. You must make your method and working clear.
- Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy's route.