| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 8 |
| 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 requiring only mechanical execution of the learned procedure on a small network (10 nodes). Part (b) is trivial arithmetic adding times together. No problem-solving insight or novel thinking required—pure algorithmic recall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| Correct order of labelling with working values shown | M1 | Must see evidence of algorithm being applied |
| A=0, B=6, C=4, E=8, D=13, G=10, H=11, F=16, I=16, J=22 | A1 | Correct permanent labels |
| All temporary labels correctly updated at each stage | A1 | |
| Correct rejection of longer paths shown | M1 | |
| Shortest time = 22 minutes | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| \(A \to C \to E \to G \to I \to J\) | B1 | ft from (i) |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| Time from D to A: shortest path needed, then add 3 minutes loading + 22 minutes A to J | M1 | Must use their answer to (a)(i) |
| \(10{:}30 +\) (time D to A) \(+ 3 + 22\) minutes | A1 | cao – dependent on correct network reading |
## Question 4:
**(a)(i)** Dijkstra's algorithm applied to network from A to J
| Working | Mark | Guidance |
|---------|------|----------|
| Correct order of labelling with working values shown | M1 | Must see evidence of algorithm being applied |
| A=0, B=6, C=4, E=8, D=13, G=10, H=11, F=16, I=16, J=22 | A1 | Correct permanent labels |
| All temporary labels correctly updated at each stage | A1 | |
| Correct rejection of longer paths shown | M1 | |
| Shortest time = 22 minutes | A1 | cao |
**(a)(ii)** Route from A to J
| Working | Mark | Guidance |
|---------|------|----------|
| $A \to C \to E \to G \to I \to J$ | B1 | ft from (i) |
**(b)** Arrival time at station
| Working | Mark | Guidance |
|---------|------|----------|
| Time from D to A: shortest path needed, then add 3 minutes loading + 22 minutes A to J | M1 | Must use their answer to (a)(i) |
| $10{:}30 +$ (time D to A) $+ 3 + 22$ minutes | A1 | cao – dependent on correct network reading |
---4 The network opposite shows roads connecting 10 villages, $A , B , \ldots , J$. The time taken to drive along a road is not proportional to the length of the road. The number on each edge shows the average time, in minutes, to drive along each road.
\begin{enumerate}[label=(\alph*)]
\item A commuter wishes to drive from village $A$ to the railway station at $J$.
\begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm, on the diagram opposite, to find the shortest driving time from $A$ to $J$.
\item State the corresponding route.
\end{enumerate}\item A taxi driver is in village $D$ at 10.30 am when she receives a radio call asking her to pick up a passenger at village $A$ and take him to the station at $J$. Assuming that it takes her 3 minutes to load the passenger and his luggage, at what time should she expect to arrive at the station?\\[0pt]
[2 marks]
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-09_2484_1717_223_150}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2015 Q4 [8]}}