1 Satellite navigation systems (sat navs) use a version of Dijkstra's algorithm to find the shortest route between two places. A simplified map is shown below. The values marked represent road distances, in km , for that section of road (from a place to a road junction, or between two places).
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ccb12789-cd5f-40dc-9f10-f8bb45399580-2_712_1386_431_335}
\captionsetup{labelformat=empty}
\caption{Fort Effleigh (F)}
\end{figure}
- Use the map to construct a network with exactly 10 arcs to show the direct distances between these places, with no road junctions shown. For example, there will need to be an arc connecting \(A\) to \(B\) of weight 22, and also arcs connecting \(A\) to \(C , D\), and \(E\). There is no arc connecting \(A\) to \(F\) (because there is no route from \(A\) to \(F\) that does not pass through another place).
- Apply Dijkstra's algorithm, starting at \(A\), to find the shortest route from \(A\) to \(F\).
Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ).
- If it takes 3 seconds for a certain sat nav to find the shortest route between two places when it has to process 200 places, calculate approximately how many minutes it will take when it has to process 4000 places.