3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4814ebd7-f48a-49cf-8ca2-045d84abd63c-4_677_1100_212_479}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
[The total weight of the network is 458]
Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.
- Use Dijkstra's algorithm to find the shortest path from A to J.
- State the length of the shortest path from A to J .
The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
- By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice.
If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
- Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.