| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| 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 part a) then analyzing how a new edge affects shortest paths by setting up and solving inequalities. Part (b) demands understanding of when new edges do/don't improve paths, requiring problem-solving beyond algorithm execution—moderately challenging for D1 level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied correctly from source | M1 | SCA |
| 3 correct values at \(C\) | M1 | |
| 3 correct values at \(E\) | M1 | |
| 3 correct values at \(H\) | M1 | |
| 3 correct values at \(J\) | M1 | |
| Final value 30 at \(J\) | A1 | 6 30 at \(J\) (dependent on first M1) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Use of \(x+5\) or \(x+11\) | M1 | |
| \((AG):\ 5+x < 25\) or \(x < 20\) | A1 | |
| \((AJ):\ 11+x \geq 30\) or \(x \geq 19\) | A1 | |
| \(x = 19\) | B1 | 4 |
| Total: 10 |
## Question 6(a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied correctly from source | M1 | SCA |
| 3 correct values at $C$ | M1 | |
| 3 correct values at $E$ | M1 | |
| 3 correct values at $H$ | M1 | |
| 3 correct values at $J$ | M1 | |
| Final value 30 at $J$ | A1 | **6** 30 at $J$ (dependent on first M1) |
## Question 6(b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Use of $x+5$ or $x+11$ | M1 | |
| $(AG):\ 5+x < 25$ or $x < 20$ | A1 | |
| $(AJ):\ 11+x \geq 30$ or $x \geq 19$ | A1 | |
| $x = 19$ | B1 | **4** |
| **Total: 10** | | |6 [Figure 1, printed on a separate sheet, is provided for use in this question.]\\
A theme park is built on two levels. The levels are connected by a staircase. There are five rides on each of the levels. The diagram shows the ten rides: $A , B , \ldots \ldots J$. The numbers on the edges represent the times, in minutes, taken to travel between pairs of rides.\\
\includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-05_984_1593_584_226}
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from $A$ to $J$.
\item A new staircase is built connecting rides $B$ and $G$. The time taken to travel from $B$ to $G$ using this staircase is $x$ minutes, where $x$ is an integer. The time taken to travel from $A$ to $G$ is reduced, but the time taken to travel from $A$ to $J$ is not reduced.
Find two inequalities for $x$ and hence state the value of $x$.\\
(4 marks)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q6 [8]}}