| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm with no complications—a standard textbook exercise requiring only methodical execution of a learned procedure. The 6 marks reflect the working steps rather than conceptual difficulty, and part (b) is trivial once (a) is complete. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dynamic programming table started correctly | M1 | SCA |
| 2 correct values at \(B\) | A1 | |
| 3 values at \(D\) | M1 | |
| 2 values at \(I\) | M1 | |
| All correct | A1 | |
| \(50\) at \(J\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route \(ACEDFGHIJ\) | B1 |
## Question 5:
### Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dynamic programming table started correctly | M1 | SCA |
| 2 correct values at $B$ | A1 | |
| 3 values at $D$ | M1 | |
| 2 values at $I$ | M1 | |
| All correct | A1 | |
| $50$ at $J$ | B1 | |
**Total: 6 marks**
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route $ACEDFGHIJ$ | B1 | |
**Total: 1 mark**
---5 [Figure 1, printed on the insert, is provided for use in this question.]\\
The network shows the times, in minutes, to travel between 10 towns.\\
\includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-05_412_1561_568_233}
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from $A$ to $J$.\\
(6 marks)
\item State the corresponding route.\\
(1 mark)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q5 [7]}}