| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming minimax route |
| Difficulty | Standard +0.3 This is a standard minimax route problem from D2, requiring systematic application of a tabular algorithm to find the route minimizing the maximum arc weight. While it involves multiple steps (8 marks for the table), the procedure is algorithmic and follows a well-defined method taught in the specification with no novel problem-solving required. |
| Spec | 7.04d Travelling salesman lower bound: using minimum spanning tree |
\includegraphics{figure_2}
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 minimax 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 Q3 [10]}}