3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-06_764_1136_258_466}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
[The total weight of the network is 413]
Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.
- Use Dijkstra's algorithm to find the shortest path from A to J.
Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K.
Abi wishes to minimise the total distance required to traverse every track.
- By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must
- state which tracks she will repeat in her route
- state the total length of her route
The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H.
Tarig wishes to minimise the total length of his inspection route. - Determine which route, Abi's or Tarig's, is shorter. You must make your working clear.