4. This question should be answered on the sheet provided in the answer booklet.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{6d306129-6e1f-424a-b21c-1bf6434ee082-5_732_1238_446_391}
\end{figure}
The weighted network shown in Fig. 3 models the area in which Bill lives. Each vertex represents a town. The edges represent the roads between the towns. The weights are the lengths, in km , of the roads.
- Use Dijkstra's algorithm to find the shortest route from Bill's home at \(S\) to \(T\). Complete all the boxes on the answer sheet and explain clearly how you determined the path of least weight from your labelling.
Bill decides that on the way to \(T\) he must visit a shop in town \(E\).
- Obtain his shortest route now, giving its length and explaining your method clearly.