4 The network below represents a small village. The arcs represent the streets and the weights on the arcs represent distances in km .
\includegraphics[max width=\textwidth, alt={}, center]{7ca6d572-d776-4ad7-a0ed-9ec43c975585-04_503_1179_324_482}

1. Use Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). 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 \(G\). Hannah wants to deliver newsletters along every street; she will start and end at \(A\).
2. Which standard network problem does Hannah need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 3.7 km .
3. Hannah knows that she will need to travel \(A B\) and \(E F\) twice, once in each direction. With this information, use an appropriate algorithm to find the length of the shortest route that Hannah can use. Show all your working. (You may find the lengths of shortest paths between vertices by inspection.) There are street name signs at each vertex except for \(A\) and \(E\). Hannah's friend Peter wants to check that the signs have not been vandalised. He will start and end at \(B\). The table below shows the complete set of shortest distances between vertices \(B , C , D , F\) and \(G\).

   	\(B\)	\(C\)	\(D\)	\(F\)	\(G\)
   \(B\)	-	0.2	0.1	0.3	0.75
   \(C\)	0.2	-	0.3	0.5	0.95
   \(D\)	0.1	0.3	-	0.2	0.65
   \(F\)	0.3	0.5	0.2	-	0.45
   \(G\)	0.75	0.95	0.65	0.45	-

4. Apply the nearest neighbour method to this table, starting from \(B\), to find an upper bound for the distance that Peter must travel.
5. Apply Prim's algorithm to the matrix formed by deleting the row and column for vertex \(G\) from the table. Start building your tree at vertex \(B\). Draw your tree. Give the order in which vertices are built into your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Peter must travel.