| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2002 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming minimax route |
| Difficulty | Standard +0.3 This is a standard textbook application of dynamic programming to find a minimax route through a network. The algorithm is mechanical (working through stages, recording minimum of maximum values), requires no novel insight, and is a routine D2 topic with straightforward execution. Slightly easier than average due to its algorithmic nature. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
3.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-03_764_1514_283_141}
\end{center}
\end{figure}
The network in Fig. 2 shows possible routes that an aircraft can take from $S$ to $T$. The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the rninimax route.
\begin{enumerate}[label=(\alph*)]
\item Complete the table in the answer booklet.\\
(8)
\item Hence obtain the minimax route from $S$ to $T$ and state the maximum amount of fuel used on any part of this route.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2002 Q3 [10]}}