5. This question should be answered on the sheet provided.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-05_956_1561_312_242}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\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.
\begin{enumerate}[label=(\alph*)]
\item 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:
\begin{enumerate}[label=(\roman*)]
\item the order in which you labelled the vertices,
\item 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.
\end{enumerate}\item 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)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1  Q5 [12]}}