5. This question should be answered on the sheet provided.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-05_956_1561_312_242}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{figure}
Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.
- Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\).
You must show clearly:
- the order in which you labelled the vertices,
- how you found a route of minimum length from your labelling.
Each night a security guard walks along each of the paths in Figure 2 at least once.
- The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
(4 marks)