| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.5 This is a standard Dijkstra's algorithm application with a straightforward extension requiring the student to find the shortest path via an intermediate vertex (A→G→J). Part (a) is routine algorithmic execution, and part (b) requires minimal additional insight—simply finding A→G + G→J using results from part (a) or repeating the algorithm. This is typical D1 examination fare, slightly easier than average A-level maths due to being purely algorithmic with no proof or novel problem-solving required. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Dijkstra's algorithm applied correctly — big replaced by small in working values at least once at D or F or I or J | M1 | Big replaced by small in working values at least once |
| A, B, C, H boxes all correct (condone lack of 0 in A's working value) | A1(BCH) | A, B, C, H boxes all correct |
| E and D ft, based on their order of labelling | A1ft(DE) | Penalise order of labelling only once |
| G and F ft, based on their order of labelling | A1ft(FG) | Penalise order of labelling only once |
| I and J CAO | A1(IJ) | Penalise order of labelling only once |
| Route ACHFIJ | B1 | Route CAO |
| 114 minutes | B1ft | 114, or their final value ft |
| 7 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Route: ABEGIJ | B1 | Route CAO |
| Length 115 (minutes) | B1 | Length CAO |
| 2 |
# Question 4:
## Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied correctly — big replaced by small in working values at least once at D or F or I or J | M1 | Big replaced by small in working values at least once |
| A, B, C, H boxes all correct (condone lack of 0 in A's working value) | A1(BCH) | A, B, C, H boxes all correct |
| E and D ft, based on their order of labelling | A1ft(DE) | Penalise order of labelling only once |
| G and F ft, based on their order of labelling | A1ft(FG) | Penalise order of labelling only once |
| I and J CAO | A1(IJ) | Penalise order of labelling only once |
| Route ACHFIJ | B1 | Route CAO |
| 114 minutes | B1ft | 114, or their final value ft |
| | **7** | |
## Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Route: ABEGIJ | B1 | Route CAO |
| Length 115 (minutes) | B1 | Length CAO |
| | **2** | |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e02c4a9a-d2ab-489f-b838-9b4d902c4457-5_679_1420_228_312}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
Figure 5 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Olivia wishes to travel from A to J as quickly as possible.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the shortest route.
On a particular day Olivia must include G in her route.
\item Find a route of minimal time from A to J that includes G , and state its length
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q4 [9]}}