| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm with clear instructions and a provided diagram. It requires mechanical execution of a standard algorithm with no problem-solving insight or novel thinking—students simply follow the procedure they've learned. The 6 marks reflect the working steps rather than conceptual difficulty, making this easier than average for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Identify odd vertices | B1 | States odd vertices (need to find which vertices are odd degree) |
| Consider pairings of odd vertices and find shortest connection | M1 | Correct method for finding repeated edges |
| Optimal pairing identified with correct total | A1 | Correct pairing chosen |
| Total = \(1400 +\) (repeated edges) | M1 | Adding repeated path to total |
| Correct final answer | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| States correct number of times through \(C\) | B1 | ft from optimal route found in (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| States correct number of times through \(D\) | B1 | ft from optimal route found in (a) |
# Question 5:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| Identify odd vertices | B1 | States odd vertices (need to find which vertices are odd degree) |
| Consider pairings of odd vertices and find shortest connection | M1 | Correct method for finding repeated edges |
| Optimal pairing identified with correct total | A1 | Correct pairing chosen |
| Total = $1400 +$ (repeated edges) | M1 | Adding repeated path to total |
| Correct final answer | A1 | |
## Part (b)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| States correct number of times through $C$ | B1 | ft from optimal route found in (a) |
## Part (b)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| States correct number of times through $D$ | B1 | ft from optimal route found in (a) |
---5 [Figure 1, printed on the insert, is provided for use in this question.]\\
The network shows the times, in minutes, to travel between 10 towns.\\
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-006_412_1561_568_233}
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from $A$ to $J$.\\
(6 marks)
\item State the corresponding route.\\
(1 mark)
\end{enumerate}
\hfill \mbox{\textit{AQA D1 Q5}}