3 Five towns, 1, 2, 3, 4 and 5, are connected by direct routes as shown. The arc weights represent distances.
\includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-4_632_540_312_744}

1. The printed answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex 5 to vertex 2.
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 4 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
3. Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
4. Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
5. Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
6. Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.