\(\mathbf { 5 }\) & 4 & - & - & 2
\hline
\end{tabular}
\end{center}
(iii) Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
(iv) Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
(v) (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
(B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
(vi) By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
(vii) In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route.
4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC .
The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.
| Driving times | to A | to W |
| From G | 20 min | 15 min |
| \multirow{2}{*}{Train journey} | To V | To LB |
| normal time | probability of delay | delay | normal time | probability of delay | delay |
| From A | 1 hr 40 min | 0.05 | 10 min | 1 hr 45 min | 0.05 | 10 min |
| From W | 1 hr 30 min | 0.10 | 20 min | 1 hr 35 min | 0.10 | 20 min |
| \multirow{2}{*}{} | To KC |
| \cline { 2 - 4 } | normal time | probability of delay | delay |
| From V | 7 min | 0.20 | 2 min |
| From LB | 9 min | 0.10 | 2 min |
Helen wants to choose the route which will give the shortest expected journey time.
(i) Draw a decision tree to model Helen's decisions and the possible outcomes.
(ii) Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time.
As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
(iii) Find the value of the radio information, explaining your calculation.
(iv) Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?