| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Combined Dijkstra and route inspection |
| Difficulty | Standard +0.3 This is a straightforward application of two standard D1 algorithms (Dijkstra's and Chinese Postman) with no novel problem-solving required. The question provides helpful information (total edge weights, D to H distance) and follows a typical textbook structure, making it slightly easier than average despite being multi-part. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied (forward) | M1 | SCA (forward) / SCA (reverse) |
| 3 values at \(F\) correct | m1 | 2 or 3 values at \(F\) |
| 2 values at \(I\) correct | m1 | 1 or 2 values at \(C\) |
| 3 values at \(J\) correct | m1 | 2 values at \(A\) |
| All correct | A1 | |
| Value \(46\) at \(K\) | B1 | |
| Total: 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route \(ABEIK\) | B1 | Allow \(KIEBA\) |
| Total: 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Consider \(A, D, K, H\) | B1 | PI |
| \(AD+KH=27+30=57\) | M1 | |
| \(AH+DK=20+20=40\) | A2,1,0 | |
| \(AK+DH=46+40=86\) | ||
| Total: \(308+40=348\) | B1 | |
| Total: 5 |
## Question 4:
### Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied (forward) | M1 | SCA (forward) / SCA (reverse) |
| 3 values at $F$ correct | m1 | 2 or 3 values at $F$ |
| 2 values at $I$ correct | m1 | 1 or 2 values at $C$ |
| 3 values at $J$ correct | m1 | 2 values at $A$ |
| All correct | A1 | |
| Value $46$ at $K$ | B1 | |
| **Total: 6** | | |
### Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route $ABEIK$ | B1 | Allow $KIEBA$ |
| **Total: 1** | | |
### Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Consider $A, D, K, H$ | B1 | PI |
| $AD+KH=27+30=57$ | M1 | |
| $AH+DK=20+20=40$ | A2,1,0 | |
| $AK+DH=46+40=86$ | | |
| Total: $308+40=348$ | B1 | |
| **Total: 5** | | |
---4 [Figure 2, printed on the insert, is provided for use in this question.]\\
The network shows 11 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges.\\
\includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-04_1762_1056_516_484}
The total of all of the times is 308 minutes.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on Figure 2 to find the minimum time to travel from $A$ to $K$.
\item State the corresponding route.
\end{enumerate}\item Find the length of an optimum Chinese postman route around the network, starting and finishing at $A$. (The minimum time to travel from $D$ to $H$ is 40 minutes.)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q4 [12]}}