6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-07_728_1465_248_301}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
In Figure 4 the weights on the arcs represent distances.
- Use Dijkstra's algorithm to find the shortest path from A to H .
- State the length of the shortest path from A to H .
One application of Dijkstra's algorithm has order \(n ^ { 2 }\), where \(n\) is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra's algorithm from each node of the network.
It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
- Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.
- Explain why your answer to part (b) can only be an approximation.