1.
| \cline { 2 - 7 }
\multicolumn{1}{c|}{} | A | B | C | D | E | F |
| A | - | 53 | 47 | 39 | 35 | 40 |
| B | 53 | - | 32 | 46 | 41 | 43 |
| C | 47 | 32 | - | 51 | 47 | 37 |
| D | 39 | 46 | 51 | - | 36 | 49 |
| E | 35 | 41 | 47 | 36 | - | 42 |
| F | 40 | 43 | 37 | 49 | 42 | - |
The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D , and wishes to minimise the total distance she travels.
- Starting at D , use the nearest neighbour algorithm to obtain an upper bound for the length of the route. You must state your route and its length.
- Starting by deleting D , and all of its arcs, find a lower bound for the route length.