| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Multiple paths of same minimum weight |
| Difficulty | Challenging +1.2 This question requires applying Dijkstra's algorithm (a standard D1 procedure) and then solving simultaneous equations to find x and y. While it involves multiple steps and the constraint that three routes have equal minimum weight adds complexity, the algorithmic application is routine and the algebra is straightforward once the three paths are identified. It's moderately harder than average due to the parameter-solving aspect, but remains a standard exam question type. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| SCA cancelling at \(C\) (PI) | M1 | |
| Correct values at \(C\) | A1 | |
| 3 values at \(G\) | m1 | |
| Correct values at \(G\) | A1 | |
| 2 values at both \(E\) and \(I\) | m1 | |
| All correct, with no extra values, and including \(18+x+y\) boxed at \(K\) | A1 | |
| 50 at \(M\) | B1 | 7 |
| Answer | Marks | Guidance |
|---|---|---|
| \(3x+y\ (=22)\) OE; \(x+y\ (=12)\) OE | M1 | Setting up simultaneous equations |
| \(\therefore x=5,\ y=7\) | A1+1 | 3 |
## Question 7:
### Part (a)
| SCA cancelling at $C$ (PI) | M1 | |
| Correct values at $C$ | A1 | |
| 3 values at $G$ | m1 | |
| Correct values at $G$ | A1 | |
| 2 values at both $E$ and $I$ | m1 | |
| All correct, with no extra values, and including $18+x+y$ boxed at $K$ | A1 | |
| 50 at $M$ | B1 | 7 | Diagram takes precedence over answer book |
### Part (b)
| $3x+y\ (=22)$ OE; $x+y\ (=12)$ OE | M1 | Setting up simultaneous equations |
| $\therefore x=5,\ y=7$ | A1+1 | 3 | CSO; SC $x=5,\ y=7$ with no working $3/3$ |
---7 [Figure 2, printed on the insert, is provided for use in this question.]\\
The following network has 13 vertices and 24 edges connecting some pairs of vertices. The number on each edge is its weight.
The weights on the edges $G K$ and $L M$ are functions of $x$ and $y$, where $x > 0 , y > 0$ and $10 < x + y < 27$.\\
\includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-7_1218_1431_660_312}
There are three routes from $A$ to $M$ of the same minimum total weight.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm on Figure 2 to find this minimum total weight.
\item Find the values of $x$ and $y$.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2010 Q7 [10]}}