3. The table below shows the least distances, in km, between six towns, A, B, C, D, E and F.
| A | B | C | D | E | F |
| A | - | 57 | 76 | 59 | 72 | 65 |
| B | 57 | - | 67 | 80 | 66 | 76 |
| C | 76 | 67 | - | 71 | 83 | 80 |
| D | 59 | 80 | 71 | - | 77 | 78 |
| E | 72 | 66 | 83 | 77 | - | 69 |
| F | 65 | 76 | 80 | 78 | 69 | - |
Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.
- Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei's route. You must state the shortcut(s) you use and the length of your upper bound.
- Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Mei's route.
- Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei's route. Make your method clear.