| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with vertex or edge exclusion |
| Difficulty | Moderate -0.3 This is a straightforward application of Dijkstra's algorithm with standard variations (visiting a specific vertex, excluding a vertex). Part (a) is routine algorithm execution, part (b) requires running Dijkstra twice (A to D, then D to K) which is a common textbook exercise, and part (c) simply involves removing vertex I and re-running the algorithm. All parts are mechanical with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct working values and order of permanent labels at each vertex | M1 | Must show Dijkstra's method |
| Correct permanent labels: \(B=16, C=14, D=35, E=37, F=37, G=28, H=28, I=46, J=46, K=60\) | A1 A1 A1 | |
| All labels correct | A1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: \(A \to C \to G \to H \to K\) (or equivalent minimum path) | B1 | Follow through from (a)(i) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum time via \(D\): \(A \to D\) shortest \(+ D \to K\) shortest \(= 35 + \text{remainder}\) | M1 | |
| Correct minimum time stated | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Remove all edges connected to \(I\); find new shortest path | M1 | |
| Minimum time and correct route stated | A1 |
# Question 3:
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct working values and order of permanent labels at each vertex | M1 | Must show Dijkstra's method |
| Correct permanent labels: $B=16, C=14, D=35, E=37, F=37, G=28, H=28, I=46, J=46, K=60$ | A1 A1 A1 | |
| All labels correct | A1 A1 | |
## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: $A \to C \to G \to H \to K$ (or equivalent minimum path) | B1 | Follow through from (a)(i) |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum time via $D$: $A \to D$ shortest $+ D \to K$ shortest $= 35 + \text{remainder}$ | M1 | |
| Correct minimum time stated | A1 | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Remove all edges connected to $I$; find new shortest path | M1 | |
| Minimum time and correct route stated | A1 | |3 The network below shows 11 towns, $A , B , \ldots , K$. The number on each edge shows the time, in minutes, to travel between a pair of towns.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the diagram below to find the minimum time to travel from $A$ to $K$.
\item State the corresponding route.
\end{enumerate}\item On a particular day, Jenny travels from $A$ to $K$ but visits her friend at $D$ on her way. Find Jenny's minimum travelling time.
\item On a different day, all roads connected to $I$ are closed due to flooding. Jenny does not visit her friend at $D$. Find her minimum time to travel from $A$ to $K$. State the route corresponding to this minimum time.\\[0pt]
[2 marks]
\section*{Answer space for question 3}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-06_1478_1548_1213_239}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2014 Q3 [10]}}