| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Standard +0.3 This is a straightforward application of two standard D1 algorithms (Dijkstra and Chinese Postman) with no novel problem-solving required. Part (a) is routine Dijkstra execution, and part (b) follows the standard Chinese Postman procedure of identifying odd vertices and finding minimum pairings. Both are textbook exercises that test algorithmic execution rather than insight, making this slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Correct order of labelling vertices | B1 | G labelled 0 first |
| Working values shown at each vertex | M1 | Must show evidence of algorithm |
| Correct permanent labels: \(G=0, K=7, H=6, D=10, I=10, B=16, F=11, L=16, C=21, A=23, E=21, J=28\) | A5 | A1 each for correct values (allow one error) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| From \(A\): \(A \to B \to K \to G\) time = 23 | B1 | ft from (a)(i) |
| From \(E\): \(E \to C \to B \to K \to G\) time = 21 | B1 | ft from (a)(i) |
| From \(J\): \(J \to I \to K \to G\) time = 28 | B1 | ft from (a)(i) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Identify odd vertices | B1 | Correct odd vertices identified |
| List pairings of odd vertices | M1 | At least two pairings considered |
| Find shortest path between each pair | M1 | Correct method |
| Select minimum weight matching | A1 | Correct pairing chosen |
| Extra weight added to total | M1 | Their extra + 134 |
| Total time = \(134 + \text{extra}\) | A1 | Correct final answer |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(B\) appears twice | B1 | cao |
## Question 5:
### Part (a)(i) – Dijkstra's Algorithm from G
| Answer/Working | Marks | Guidance |
|---|---|---|
| Correct order of labelling vertices | B1 | G labelled 0 first |
| Working values shown at each vertex | M1 | Must show evidence of algorithm |
| Correct permanent labels: $G=0, K=7, H=6, D=10, I=10, B=16, F=11, L=16, C=21, A=23, E=21, J=28$ | A5 | A1 each for correct values (allow one error) |
### Part (a)(ii) – Routes
| Answer/Working | Marks | Guidance |
|---|---|---|
| From $A$: $A \to B \to K \to G$ time = 23 | B1 | ft from (a)(i) |
| From $E$: $E \to C \to B \to K \to G$ time = 21 | B1 | ft from (a)(i) |
| From $J$: $J \to I \to K \to G$ time = 28 | B1 | ft from (a)(i) |
### Part (b)(i) – Chinese Postman
| Answer/Working | Marks | Guidance |
|---|---|---|
| Identify odd vertices | B1 | Correct odd vertices identified |
| List pairings of odd vertices | M1 | At least two pairings considered |
| Find shortest path between each pair | M1 | Correct method |
| Select minimum weight matching | A1 | Correct pairing chosen |
| Extra weight added to total | M1 | Their extra + 134 |
| Total time = $134 + \text{extra}$ | A1 | Correct final answer |
### Part (b)(ii) – Vertex B
| Answer/Working | Marks | Guidance |
|---|---|---|
| $B$ appears **twice** | B1 | cao |
---5 The network on the page opposite shows the times, in minutes, taken by police cars to drive along roads connecting 12 places, $A , B , \ldots , L$.
On a particular day, there are three police cars in the area at $A , E$ and $J$. There is an emergency at $G$ and all three police cars drive to $G$.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the network, starting from $\boldsymbol { G }$, to find the minimum driving time for each of the police cars to arrive at $G$.
\item For each of the police cars, write down the route corresponding to the minimum driving time in your answer to part (a)(i).
\end{enumerate}\item Each day, a police car has to drive along each road at least once, starting and finishing at $A$.
For an optimal Chinese postman route:
\begin{enumerate}[label=(\roman*)]
\item find the driving time for the police car;
\item state the number of times that the vertex $B$ would appear.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-13_2486_1709_221_153}
\end{center}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q5 [17]}}