| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.8 This is a standard textbook application of dynamic programming to find shortest paths in a small network. The algorithm is mechanical (working backwards from T), requires no novel insight, and the presence of negative edges doesn't fundamentally change the straightforward tabulation process. Easier than average A-level content. |
| Spec | 7.05e Cascade charts: scheduling and effect of delays |
5 [Figure 3, printed on the insert, is provided for use in this question.]\\
The following network shows 11 vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown.\\
\includegraphics[max width=\textwidth, alt={}, center]{68ff5b50-6aff-4b28-8fad-d16a8bb4779e-05_824_1504_559_278}
\begin{enumerate}[label=(\alph*)]
\item Working backwards from $\boldsymbol { T }$, use dynamic programming to find the minimum cost of travelling from $S$ to $T$. You may wish to complete the table on Figure 3 as your solution.
\item State the minimum cost and the routes corresponding to this minimum cost.
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2008 Q5 [9]}}