- Arthur is planning a bus journey from town \(A\) to town \(L\). There are various routes he can take but he will have to change buses three times - at \(B , C\) or \(D\), at \(E , F , G\) or \(H\) and at \(I , J\) or \(K\).
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{06378fdc-2d77-4bdc-810a-1ce9de180c3d-3_760_1410_351_315}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{figure}
Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the total waiting time is as small as possible.
Use dynamic programming to find the route that Arthur should use.