2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-03_892_871_203_596}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 represents a network of roads between ten villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.
- Use Dijkstra's algorithm to find the shortest route from A to J. State the route and its length.
During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.
- Use Prim's algorithm, starting at A , to find a minimum connector for the five villages \(\mathrm { A } , \mathrm { B }\), C, D and E. You must clearly state the order in which you select the edges of your minimum connector.
- Use Kruskal's algorithm to find a minimum connector for the five villages \(\mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.
- Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.