| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 14 |
| 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 and route inspection) with minimal problem-solving required. Part (a) is routine Dijkstra execution, part (b)(i) is simple inspection of a small network, and part (b)(ii) is textbook route inspection (identify odd vertices, pair them optimally, add to total). The question provides the sum of all edges and requires only mechanical application of learned procedures, making it slightly easier than average for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Diagram with SCA; 4 values at \(I\); 2 values at \(M\); 2 values at \(O\) | M1, M1, M1, M1, A1, B1 | 465 at \(O\) (6 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| CASINO | B1 | Or ONISAC (1 mark total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(A \to M = 255\) | B1 | (1 mark total) |
| Answer | Marks | Guidance |
|---|---|---|
| Odds \((C, A, S, M)\) with \(CA + SM = 270\), \(CS + AM = 390\), \(CM + AS = 390\), Min \(2280 + 270 = 2550\) | M1, A3, M1, A1 | PI; (−1 EE) 2280 + their best pairing; SC 2/6 for answer 2550 with no working (6 marks total) |
**7(a)(i)**
| Diagram with SCA; 4 values at $I$; 2 values at $M$; 2 values at $O$ | M1, M1, M1, M1, A1, B1 | 465 at $O$ (6 marks total) |
**7(a)(ii)**
| CASINO | B1 | Or ONISAC (1 mark total) |
**7(b)(i)**
| $A \to M = 255$ | B1 | (1 mark total) |
**7(b)(ii)**
| Odds $(C, A, S, M)$ with $CA + SM = 270$, $CS + AM = 390$, $CM + AS = 390$, Min $2280 + 270 = 2550$ | M1, A3, M1, A1 | PI; (−1 EE) 2280 + their best pairing; SC 2/6 for answer 2550 with no working (6 marks total) |7 [Figure 2, printed on the insert, is provided for use in this question.]\\
The network shows the times, in seconds, taken by Craig to walk along walkways connecting ten hotels in Las Vegas.\\
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-07_1435_1267_525_351}
The total of all the times in the diagram is 2280 seconds.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Craig is staying at the Circus ( $C$ ) and has to visit the Oriental ( $O$ ).
Use Dijkstra's algorithm on Figure 2 to find the minimum time to walk from $C$ to $O$.
\item Write down the corresponding route.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Find, by inspection, the shortest time to walk from $A$ to $M$.
\item Craig intends to walk along all the walkways. Find the minimum time for Craig to walk along every walkway and return to his starting point.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q7 [14]}}