4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-05_841_1201_226_431}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.
- Use Dijkstra's algorithm to find the shortest path from A to F . State your path and its length.
On another day, Sarah wishes to travel from A to F via J.
- Find a route of minimal length that goes from A to F via J and state its length.
- Use Prim's algorithm, starting at G , to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
- State the length, in miles, of the minimum spanning tree.