6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{27296f39-bd03-47ff-9a5e-c2212d0c68ed-08_832_1171_169_445}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
[The total weight of the network is \(383 + x\) ]
Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\), H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible.
The time taken to travel between towns G and J is unknown and is denoted by \(x\) minutes.
Dijkstra's algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 in the answer book the "Order of labelling" and "Final value" at A and J, and the "Working values" at J , have already been completed.
- Use Dijkstra's algorithm to find the fastest time to travel from A to H . State the quickest route.
Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A . It is given that his route will take at least 440 minutes.
- Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of \(x\).
- Write down a possible route for Ezra.
A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A . It is given that this inspection route takes exactly 488 minutes.
- Determine the value of \(x\). You must give reasons for your answer.