| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Combined Dijkstra and route inspection |
| Difficulty | Moderate -0.3 This is a standard D1 question testing two algorithmic procedures (Dijkstra's and Chinese Postman) that students practice extensively. While it requires careful execution across multiple steps and the network has 13 vertices, both algorithms are mechanical applications of learned procedures with no novel problem-solving or insight required. The Chinese Postman part is slightly more involved than basic textbook exercises, but remains routine for D1 students who have practiced these standard exam questions. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges.
The total of all the times is 384 minutes.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm on the network below, starting from $M$, to find the minimum time to travel from $M$ to each of the other towns. [7 marks]
\item
\begin{enumerate}[label=(\roman*)]
\item Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at $M$. [6 marks]
\item State the number of times that the vertex $F$ would appear in a corresponding route. [1 mark]
\end{enumerate}
\end{enumerate}
\includegraphics{figure_4}
\hfill \mbox{\textit{AQA D1 2010 Q4 [14]}}