| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.8 This is a standard D1 Dijkstra's algorithm question with routine extensions. Part (a) is textbook application of the algorithm (6 marks for showing working), part (b) simply requires comparing two paths already found, and part (c) asks for a conceptual explanation (add 2 to each vertex weight) rather than execution. All parts are procedural with no novel problem-solving required, making this easier than average A-level maths. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Dijkstra's algorithm applied correctly | M1 | Larger value replaced by smaller at least once in working values at B, D, E, F or G |
| All values in boxes A, B, C, D correct with working values in correct order including order of labelling | A1 (ABCD) | — |
| All values in boxes F, E, G correct | A1 (FEG) | Penalise order of labelling errors once per question |
| All values in boxes H and T correct (follow through) | A1ft (HT) | Penalise order of labelling only once per question |
| Quickest route is ACBEGT | A1 | CAO for route |
| Length = 40 (minutes) | B1ft | Follow through on their final value at T (6) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Quickest journey A to F is ACDF | M1 | Any path A to T via their shortest path A to F |
| Quickest journey A to T via F is ACDFHT \(= 43\) (minutes) | A1 | 43 and ACDFHT (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Add 2 to each arc except GT and HT (or except AB, AC and AD) | M1, A1 | M1: valid general method — any mention of adding 2 to arc weights; A1: CAO — adding 2 to each arc except \(\{GT, HT\}\) or \(\{AB, AC, AD\}\) (2) |
# Question 3:
## Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Dijkstra's algorithm applied correctly | M1 | Larger value replaced by smaller at least once in working values at B, D, E, F or G |
| All values in boxes A, B, C, D correct with working values in correct order including order of labelling | A1 (ABCD) | — |
| All values in boxes F, E, G correct | A1 (FEG) | Penalise order of labelling errors once per question |
| All values in boxes H and T correct (follow through) | A1ft (HT) | Penalise order of labelling only once per question |
| Quickest route is **ACBEGT** | A1 | CAO for route |
| Length = **40** (minutes) | B1ft | Follow through on their final value at T **(6)** |
## Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Quickest journey A to F is ACDF | M1 | Any path A to T via **their** shortest path A to F |
| Quickest journey A to T via F is ACDFHT $= 43$ (minutes) | A1 | 43 and ACDFHT **(2)** |
## Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Add 2 to each arc except GT and HT (or except AB, AC and AD) | M1, A1 | M1: valid general method — any mention of adding 2 to arc weights; A1: CAO — adding 2 to each arc except $\{GT, HT\}$ or $\{AB, AC, AD\}$ **(2)** |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-4_591_1581_239_258}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 shows a network representing the time taken, in minutes, to travel by train between nine towns, A, B, C, D, E, F, G, H and T.
A train is to travel from A to T without stopping.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the quickest route from A to T and the time taken.\\
(6)
At present, the train travels from A to T via F without stopping.
\item Use your answer to (a) to find the quickest route from A to T via F and the time taken.\\
(2)
A train is to travel from A to T , stopping for 2 minutes at each town it passes through on its route.
\item Explain how you would adapt the network so that you could use Dijkstra's algorithm to find the quickest route for this train. You do not need to find this route.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2014 Q3 [10]}}