| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Multiple paths of same minimum weight |
| Difficulty | Standard +0.8 This question requires applying Dijkstra's algorithm systematically, then solving a system of equations to find x and y such that exactly three paths have equal minimum weight. It goes beyond routine algorithm application to require algebraic reasoning about when multiple optimal paths exist, making it moderately challenging for D1 level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (Min =) 43 | B1 | 6 |
| M1 | SCA; cancelling at 2 (or more) vertices | |
| A1 | Correct at \(D\) | |
| M1 | 2 values at \(E\) | |
| M1 | 2 values at \(G\) | |
| A1 | All correct (condone 0 missing at \(A\) and missing expressions in \(x\) and \(y\) at \(H\)) |
| Answer | Marks | Guidance |
|---|---|---|
| \(2x + y = p\) and \(3x - 2y = q\) | M1 | Obtaining a pair of equations in this form or (22) + \(2x + y = \) (43) and (22) + \(3x - 2y = \) (43). \(2x + y = 21\) and \(3x - 2y = 21\) |
| \(x = 9\) | A1 | CAO |
| \(y = 3\) | A1 | 3 |
| Total | 9 | |
| TOTAL | 75 |
## 7(a)
| (Min =) 43 | B1 | 6 | Accept 43 at $H$ |
| | | | |
| | M1 | SCA; cancelling at 2 (or more) vertices |
| | A1 | Correct at $D$ |
| | M1 | 2 values at $E$ |
| | M1 | 2 values at $G$ |
| | A1 | All correct (condone 0 missing at $A$ and missing expressions in $x$ and $y$ at $H$) |
## 7(b)
| $2x + y = p$ and $3x - 2y = q$ | M1 | Obtaining a pair of equations in this form or (22) + $2x + y = $ (43) and (22) + $3x - 2y = $ (43). $2x + y = 21$ and $3x - 2y = 21$ |
| $x = 9$ | A1 | CAO |
| $y = 3$ | A1 | 3 | CAO. NMS: both correct M1A2, one/none correct M0A0 |
| Total | | 9 |
| TOTAL | | 75 |7 [Figure 2, printed on the insert, is provided for use in this question.]\\
The following network has eight vertices, $A , B , \ldots , H$, and edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges $E H$ and $G H$ are functions of $x$ and $y$.\\
\includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-07_1170_1705_596_164}
Given that there are three routes from $A$ to $H$ with the same minimum weight, use Dijkstra's algorithm on Figure 2 to find:
\begin{enumerate}[label=(\alph*)]
\item this minimum weight;
\item the values of $x$ and $y$.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q7 [9]}}