| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Easy -1.2 This is a straightforward application of Dijkstra's algorithm, a standard D1 topic with a mechanical procedure. Part (a) requires only executing the algorithm correctly on a small network, while part (b) adds a simple time calculation. No problem-solving insight is needed—just routine application of a learned algorithm. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct working values applied at each node | M1 | |
| Correct order of labelling shown | M1 | |
| All permanent labels correct | A3 | Lose one A mark per error |
| Minimum distance \(= 29\) miles | A1 | |
| Route: \(A\)–\(C\)–\(B\)–\(E\)–\(H\)–\(J\) | A1 | (ii) correct route stated |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Time on \(AJ\) direct: \(\frac{35}{60}\) hours | M1 | Or other route time calculated correctly |
| Shortest distance route time: \(\frac{29}{50}\) hours | M1 | Using \(\text{time} = \frac{\text{distance}}{\text{speed}}\) |
| Minimum time \(= 34.8\) minutes (or \(0.58\) hours) | A1 | Accept equivalent forms |
# Question 6:
## Part (a)(i) and (ii) — Dijkstra's Algorithm
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct working values applied at each node | M1 | |
| Correct order of labelling shown | M1 | |
| All permanent labels correct | A3 | Lose one A mark per error |
| Minimum distance $= 29$ miles | A1 | |
| Route: $A$–$C$–$B$–$E$–$H$–$J$ | A1 | (ii) correct route stated |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Time on $AJ$ direct: $\frac{35}{60}$ hours | M1 | Or other route time calculated correctly |
| Shortest distance route time: $\frac{29}{50}$ hours | M1 | Using $\text{time} = \frac{\text{distance}}{\text{speed}}$ |
| Minimum time $= 34.8$ minutes (or $0.58$ hours) | A1 | Accept equivalent forms |
---6 The network opposite shows some roads connecting towns. The number on each edge represents the length, in miles, of the road connecting a pair of towns.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the network to find the minimum distance from $A$ to $J$.
\item Write down the corresponding route.
\end{enumerate}\item The road $A J$ is a dual carriageway. Ken drives at 60 miles per hour on this road and drives at 50 miles per hour on all other roads.
Find the minimum time to travel from $A$ to $J$.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-15_2487_1714_221_152}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q6 [10]}}