4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-05_999_1214_233_424}
\captionsetup{labelformat=empty}
\caption{Figure 4
[0pt]
[The total weight of the network is 85]}
\end{figure}
Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn wishes to travel from A to H. She wishes to minimise the distance she travels.
- Use Dijkstra's algorithm to find the shortest path from A to H. State the shortest path and its length.
On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.
- Use the route inspection algorithm to find the length of the shortest inspection route. State the edges that should be repeated. You should make your method and working clear.
(5)
The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A. - State the edges that should be repeated.
- State a possible route and calculate its length. You must make your method and working clear.