| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Effect of new edge on shortest paths |
| Difficulty | Standard +0.3 This is a straightforward application of Dijkstra's algorithm followed by basic arithmetic. Part (a) is standard algorithmic execution, part (b) is direct reading from the algorithm, and part (c) requires simple calculation using the constraint that the new route saves 10 miles. No novel problem-solving or geometric insight needed—slightly easier than average due to mechanical nature. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A = 0 (permanent label) | B1 | Starting vertex correctly labelled |
| Correct order of permanent labels: B=28, D=37, C=47, E=83, F=93, G=103, H=113, I=117, J=127 | M1 A1 | M1 for correct method, A1 for all correct permanent labels |
| Working values shown at each vertex (temporary labels updated correctly) | M1 A1 | M1 for evidence of working values, A1 all correct |
| Final answer: shortest distance = 127 miles | A1 | cao |
| All working shown at each vertex | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(A \to B \to D \to E \to G \to H \to I \to J\) | B1 | Follow through from (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| New shortest distance would be \(127 - 10 = 117\) miles | M1 | |
| Route via new road: \(A \to B \to G \to H \to I \to J\) or equivalent using B to G | M1 | |
| Length of B to G road: current path \(A \to B\) = 28, need \(28 + BG + \text{rest} = 117\) | A1 | BG = 23 miles, new route stated |
# Question 6:
## Part (a): Dijkstra's Algorithm A to J
| Answer | Mark | Guidance |
|--------|------|----------|
| A = 0 (permanent label) | B1 | Starting vertex correctly labelled |
| Correct order of permanent labels: B=28, D=37, C=47, E=83, F=93, G=103, H=113, I=117, J=127 | M1 A1 | M1 for correct method, A1 for all correct permanent labels |
| Working values shown at each vertex (temporary labels updated correctly) | M1 A1 | M1 for evidence of working values, A1 all correct |
| Final answer: shortest distance = 127 miles | A1 | cao |
| All working shown at each vertex | B1 | |
## Part (b): Route
| Answer | Mark | Guidance |
|--------|------|----------|
| $A \to B \to D \to E \to G \to H \to I \to J$ | B1 | Follow through from (a) |
## Part (c): New Road B to G
| Answer | Mark | Guidance |
|--------|------|----------|
| New shortest distance would be $127 - 10 = 117$ miles | M1 | |
| Route via new road: $A \to B \to G \to H \to I \to J$ or equivalent using B to G | M1 | |
| Length of B to G road: current path $A \to B$ = 28, need $28 + BG + \text{rest} = 117$ | A1 | BG = 23 miles, new route stated |
---6 The network below shows the lengths of roads, in miles, connecting 10 towns, $A , B , \ldots , J$.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm on the network to find the shortest distance from $A$ to $J$. Show all your working at each vertex.
\item Write down the corresponding route.
\item A new road is to be constructed connecting $B$ to $G$. Find the length of this new road if the shortest distance from $A$ to $J$ is reduced by 10 miles. State the new route.\\
(3 marks)\\
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-12_1846_1719_861_150}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q6 [11]}}