\(\mathbf { 5 }\) & 15 & 16 & 12 & 14 & 24
\hline
\end{tabular}
\end{center}
| \cline { 2 - 6 }
\multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | \(\mathbf { 5 }\) |
| \(\mathbf { 1 }\) | 2 | 2 | 2 | 4 | 5 |
| \(\mathbf { 2 }\) | 1 | 3 | 3 | 3 | 3 |
| \(\mathbf { 3 }\) | 2 | 2 | 2 | 4 | 5 |
| \(\mathbf { 4 }\) | 1 | 3 | 3 | 3 | 5 |
| \(\mathbf { 5 }\) | 1 | 3 | 3 | 4 | 3 |
- Perform the fourth iteration of the algorithm, and show that there is no change to either matrix in the final iteration.
- Show how to use the matrices to give the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex 2.
- Draw the complete network of shortest distances.
- Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
- By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.