| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Moderate -0.5 This is a straightforward application of two standard D1 algorithms (Chinese Postman and Dijkstra) with no novel problem-solving required. Both parts follow textbook procedures: identifying odd vertices and pairing them for part (a), and mechanically applying Dijkstra's algorithm for part (b). While it requires careful execution across multiple steps, the techniques are routine for D1 students, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Identify odd vertices | B1 | Correct identification of odd nodes |
| List pairings of odd vertices and find shortest path for each pairing | M1 | At least one correct pairing attempted |
| Correct shortest paths found for pairings | A1 | |
| Correct minimum weight matching identified | A1 | |
| Total = 2410 + repeated edges | M1 | Adding total length of roads to repeated edges |
| Correct total (answer) | A1 | 6 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct application of Dijkstra's algorithm shown | M1 | Evidence of working values |
| Correct order of permanent labelling | A1 | |
| At least 4 correct permanent labels | A1 | |
| All correct permanent labels | A1 | |
| Correct minimum distance stated | A1 | |
| Route correctly traced back | A1 | |
| Correct route stated | B1 | 7 marks total |
# Question 4:
## Part (a) – Chinese Postman Route
| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify odd vertices | B1 | Correct identification of odd nodes |
| List pairings of odd vertices and find shortest path for each pairing | M1 | At least one correct pairing attempted |
| Correct shortest paths found for pairings | A1 | |
| Correct minimum weight matching identified | A1 | |
| Total = 2410 + repeated edges | M1 | Adding total length of roads to repeated edges |
| Correct total (answer) | A1 | 6 marks total |
## Part (b) – Dijkstra's Algorithm from C to T
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct application of Dijkstra's algorithm shown | M1 | Evidence of working values |
| Correct order of permanent labelling | A1 | |
| At least 4 correct permanent labels | A1 | |
| All correct permanent labels | A1 | |
| Correct minimum distance stated | A1 | |
| Route correctly traced back | A1 | |
| Correct route stated | B1 | 7 marks total |
---4 The diagram opposite shows a network of roads on a housing estate. The number on each edge is the length, in metres, of the road.
Joe is starting a kitchen-fitting business.
\begin{enumerate}[label=(\alph*)]
\item Joe delivers leaflets advertising his business. He walks along all of the roads at least once, starting and finishing at $C$. Find the length of an optimal Chinese postman route for Joe.
\item Joe gets a job fitting a kitchen in a house at $T$. Joe starts from $C$ and wishes to drive to $T$. Use Dijkstra's algorithm on the diagram opposite to find the minimum distance to drive from $C$ to $T$. State the corresponding route.
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-08_1791_1705_916_155}\\
(b)\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-09_2395_1602_312_260}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q4 [13]}}