| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Effect of new edge on shortest paths |
| Difficulty | Standard +0.8 This question requires applying Dijkstra's algorithm (routine for D1), then analyzing how a new edge affects shortest paths by setting up and solving inequalities. The inequality reasoning requires understanding that the new bridge must reduce A→G time but not A→J time, demanding careful consideration of multiple path options and their constraints—this goes beyond mechanical algorithm application to require genuine problem-solving insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a)(i) Using Dijkstra's algorithm, with 2 values at C and 2 or 3 values at E | M1 | SCA |
| Correct values at C and at E | A1 | |
| Correct two values at G and no others | A1 | |
| All correct, including cancelling (in all forms of presentation) and boxing (condone omission of 0 at A) | A1 | |
| (ii) A D F H G | B1 | 5 marks total |
| (b) \(9 + x < 13\) or \(x < 4\) | M1 | oe |
| \(9 + x + 3 \geq 15\) or \(x \geq 3\) | M1 | oe |
| \((x =) 3\) | A1 CSO | 3 marks total |
**(a)(i)** Using Dijkstra's algorithm, with 2 values at C and 2 or 3 values at E | M1 | SCA
Correct values at C and at E | A1 |
Correct two values at G and no others | A1 |
All correct, including cancelling (in all forms of presentation) and boxing (condone omission of 0 at A) | A1 |
**(ii)** A D F H G | B1 | 5 marks total | Do NOT allow reverse order
**(b)** $9 + x < 13$ or $x < 4$ | M1 | oe
$9 + x + 3 \geq 15$ or $x \geq 3$ | M1 | oe
$(x =) 3$ | A1 CSO | 3 marks total | If M0 M0 scored then SC1 for $(x = ) 3$
**Total: 8 marks**
---5 A fair comes to town one year and sets up its rides in two large fields that are separated by a river. The diagram shows the ten main rides, at $A , B , C , \ldots , J$. The numbers on the edges represent the times, in minutes, it takes to walk between pairs of rides. A footbridge connects the rides at $D$ and $F$.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the diagram below to find the minimum time to walk from $A$ to each of the other main rides.
\item Write down the route corresponding to the minimum time to walk from $A$ to $G$.
\end{enumerate}\item The following year, the fair returns. In addition to the information shown on the diagram, another footbridge has been built to connect the rides at $E$ and $G$. This reduces the time taken to travel from $A$ to $G$, but the time taken to travel from $A$ to $J$ is not reduced.
The time to walk across the footbridge from $E$ to $G$ is $x$ minutes, where $x$ is an integer.
Find two inequalities for $x$ and hence state the value of $x$.
\section*{Answer space for question 5}
(a)(i)\\
\includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-12_659_1591_1692_223}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2016 Q5 [8]}}