4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-05_572_799_228_632}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
The network in Figure 3 shows the roads linking a depot, D, and three collection points \(\mathrm { A } , \mathrm { B }\) and C . The number on each arc represents the length, in miles, of the corresponding road. The road from B to D is a one-way road, as indicated by the arrow.
- Explain clearly if Dijkstra's algorithm can be used to find a route from D to A .
The initial distance and route tables for the network are given in the answer book.
- Use Floyd's algorithm to find a table of least distances. You should show both the distance table and the route table after each iteration.
- Explain how the final route table can be used to find the shortest route from D to B . State this route.
There are items to collect at \(\mathrm { A } , \mathrm { B }\) and C . A van will leave D to make these collections in any order and then return to D. A minimum route is required.
Using the final distance table and the Nearest Neighbour algorithm starting at D,
- find a minimum route and state its length.
Floyd's algorithm and Dijkstra's algorithm are applied to a network. Each will find the shortest distance between vertices of the network.
- Describe how the results of these algorithms differ.