7.
\includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-5_965_1657_210_121}
Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish's secret headquarters at X to safety at Y . To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, \(A , B , C , D , E , F , G , H , I , J , K\) and \(L\), at which there are air pockets where he can take a breath.
The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next.
Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.
- Use dynamic programming to complete the table below and hence find a suitable route for Agent Goodie.
Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.
- Find an optimal route for Agent Goodie avoiding tunnel XA.