3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{c8134d3b-71cb-4b92-ac54-81a4ff8f3011-05_702_1479_201_293}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
[The total weight of the network is 120]
- Explain what is meant by the term "path".
- State, with a reason, whether the network in Figure 2 is Eulerian, semi-Eulerian or neither.
Figure 2 represents a network of cycle tracks between eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc represents the length, in km , of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H.
- Use Dijkstra's algorithm to find the shortest path that Samira can take.
An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G .
Daisy plans to cycle along every track in the new network, starting and finishing at H .
Given that the addition of either track CD or track EG will not affect the final values obtained in (c), - use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must
- state which tracks Daisy will repeat in her route
- state the total length of her route