8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum.
The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road.
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}
- Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
- Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
- Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
- Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
- By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour.
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Table 1}
| \(\boldsymbol { P }\) | \(Q\) | \(\boldsymbol { R }\) | \(\boldsymbol { S }\) | \(T\) | \(\boldsymbol { U }\) |
| \(P\) | - | 25 | | | | |
| \(Q\) | 25 | - | 20 | 21 | 23 | 11 |
| \(\boldsymbol { R }\) | | 20 | - | | | |
| \(\boldsymbol { S }\) | | 21 | | - | | |
| \(T\) | | 23 | | | - | 12 |
| \(\boldsymbol { U }\) | | 11 | | | 12 | - |
\end{table}
\includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}