1.
| A | B | C | D | E | F |
| A | - | 73 | 56 | 27 | 38 | 48 |
| B | 73 | - | 58 | 59 | 43 | 34 |
| C | 56 | 58 | - | 46 | 38 | 42 |
| D | 27 | 59 | 46 | - | 25 | 32 |
| E | 38 | 43 | 38 | 25 | - | 21 |
| F | 48 | 34 | 42 | 32 | 21 | - |
The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A , and wishes to minimise the total distance he will travel.
- Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen's route. You must state your route and its length.
- Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen's route.
- Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.