4 Answer this question on the insert provided. The vertices in the network below represent the junctions between main roads near Ayton ( \(A\) ). The arcs represent the roads and the weights on the arcs represent distances in miles.
\includegraphics[max width=\textwidth, alt={}, center]{fe06fa02-9f5d-4082-8e96-feea705d3fa2-4_812_1198_443_475}

1. On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from \(A\) to \(H\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from \(A\) to \(H\) and give its length in miles. Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.
2. Which standard network problem does Simon need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 67.5 miles.
3. Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from \(A\) and ending at \(H\).
4. Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.
5. Show that the nearest neighbour method fails on this network if it is started from \(A\).
6. Apply the nearest neighbour method starting from \(C\) to find an upper bound for the distance that Amber must travel.
7. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node \(A\) and all the arcs that are directly joined to node \(A\). Start building your tree at node B. (You do not need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert. Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel.