3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-04_1059_1424_228_317}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 4 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Sally wishes to travel from A to J. She wishes to minimise the distance she travels.
- Use Dijkstra's algorithm to find the shortest path from A to J. State the path and its length.
- Find a route of minimal length that goes from D to H via A and state its length.
- Use Prim's algorithm, starting at E , to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
- Find the length, in kilometres, of your minimum spanning tree.