| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 14 |
| Paper | 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 minimal problem-solving required. Part (a) is routine Dijkstra execution, part (b)(i) is simple observation from the algorithm output, and part (b)(ii) requires identifying odd vertices and adding the shortest pairing—all mechanical procedures covered extensively in D1 teaching. The question is slightly easier than average because it explicitly tells students which algorithms to use and provides a clear structure with no conceptual traps. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
3 [Figure 1, printed on the insert, is provided for use in this question.]\\
The diagram shows roads connecting some places of interest in Berlin. The numbers represent the times taken, in minutes, to walk along the roads.\\
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-4_1427_1404_502_319}
The total of all walking times is 167 minutes.
\begin{enumerate}[label=(\alph*)]
\item Mia is staying at $D$ and is to visit $H$.
\begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from $D$ to $H$.
\item Write down the corresponding route.
\end{enumerate}\item Each day, Leon has to deliver leaflets along all of the roads. He must start and finish at $A$.
\begin{enumerate}[label=(\roman*)]
\item Use your answer to part (a) to write down the shortest walking time from $D$ to $A$.
\item Find the walking time of an optimum Chinese Postman route for Leon. (6 marks)
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q3 [14]}}