| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2024 |
| 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 methodical execution of a learned procedure on a small 9-node network. Part (b) is a simple observation about MST weight being less than shortest path weight, requiring minimal additional reasoning beyond part (a). |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Part | Answer/Working | Marks |
| 3(a) | Network diagram showing all nodes with correct working values and correct labelling in strictly increasing sequence | M1, A1 (ACBFG), A1 (DE), A1 (ft) (HJ) |
| 3(b) | Shortest time to travel from A to J is 74 (mins); Quickest route is ACBFGDEHJ | A1 (ft), A1 (6) |
| Weight of MST is 74 (mins) | M1, A1 (ft) (2) | |
| Total: 8 marks |
| Part | Answer/Working | Marks | Guidance |
|------|---|---|---|
| 3(a) | Network diagram showing all nodes with correct working values and correct labelling in strictly increasing sequence | M1, A1 (ACBFG), A1 (DE), A1 (ft) (HJ) | In (a) it is important that all values at each node are checked very carefully – the order of the working values must be correct for the corresponding A mark to be awarded e.g. at E the working values must be 71 61 52 in that order (so 71 52 61 is incorrect). It is also important that the order of labelling is checked carefully. The order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, ... will be penalised once (see notes below) but 1, 2, 3, 5, 6, ... is fine. Errors in the final values and working values are penalised before errors in the order of labelling |
| 3(b) | Shortest time to travel from A to J is 74 (mins); Quickest route is ACBFGDEHJ | A1 (ft), A1 (6) | Follow through their answer to (a) provided that the route from (a) passed through all nine nodes in the network (a weight of 74 with no reason scores M0) |
| | Weight of MST is 74 (mins) | M1, A1 (ft) (2) | |
| | **Total: 8 marks** | | |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ba9337bf-7a3c-49aa-b395-dd7818cf1d13-04_994_1616_242_223}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger 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 quickest route.\\
(6)
\item Hence determine the weight of the minimum spanning tree for the network given in Figure 2. Give a reason for your answer.
You do not need to find the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2024 Q3 [8]}}