2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-03_563_1445_214_312}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
[The total weight of the network is 299]
Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track.
One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.
- Use Dijkstra's algorithm to find the shortest path from A to K .
- State the length of the shortest path from A to K .
(6)
The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E .
- State the edges that will need to be traversed twice.
- Find the length of Blanche's route.
It is now decided to start the inspection route at A and finish at K . Blanche must minimise the length of her route and travel along each track at least once.
- By considering the pairings of all relevant nodes, find the length of Blanche's new route. You must make your method and working clear.