4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-05_876_1353_230_354}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{figure}
[The total weight of the network is 275]
Figure 5 models a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each edge gives the time, in minutes, to travel along the corresponding road. Mandeep wishes to travel from A to J as quickly as possible.
- Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route.
On Monday, Mandeep must travel from D to H via A.
- Find the shortest time needed to travel from D to H via A . State the quickest route.
On Wednesday, Mandeep needs to travel along each road to check that it is in good repair. She wishes to minimise the total time required to traverse the network. Mandeep plans to start and finish her inspection route at G.
- Use an appropriate algorithm to find the roads that need to be traversed twice. You must make your method and working clear.
- Write down a possible route, giving its duration.
On Friday, all the roads leading directly to B are closed. Mandeep needs to check all the remaining roads and may start at any village and finish at any village. A route is required that excludes all those roads leading directly to B .
- State all possible combinations of starting and finishing points so that the duration of Mandeep's route is minimised. Calculate the duration of Mandeep's minimum route.