| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.8 This is a straightforward application of standard algorithms (Dijkstra's and Prim's) taught in D1, with part (b) requiring simple addition of two shortest paths. All parts are routine textbook exercises with no novel problem-solving or insight required, making it easier than average A-level questions. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied correctly (larger value replaced by smaller at least once) | M1 | Larger value replaced by smaller value at least once at C, D, F, G, H or J |
| All values in E, B and C correct with working values in correct order at C | A1 (EBC) | Including order of labelling |
| All values F, G and D correct in correct order | A1 (FGD) | F, G and D must be labelled in that order and after A, E, B and C |
| All values in H and J correct (follow through) | A1ft (HJ) | H and J labelled in that order; H labelled after all other nodes excluding J |
| Shortest path: ABGHJ | A1 | CAO |
| Length: 56 (km) | A1ft | Follow through on final value at J |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route from D to H via A: DCBABGH | B1 | CAO |
| Length: 80 (km) | B1ft | Follow through: final value at D + final value at H |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| EF, FG, BG, CB; CD, AE; GH, HJ | M1; A1; A1 | First four arcs (or five nodes EFGBC) correctly chosen in order (M1 max if any rejections seen). First six arcs (all nodes EFGBCDAHJ) correctly chosen in order (c1A1). CSO all arcs correctly stated in correct order with no extras (c2A1) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Length of MST: 89 (km) | B1 | CAO; condone lack of or incorrect units |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied correctly (larger value replaced by smaller at least once) | M1 | Larger value replaced by smaller value at least once at C, D, F, G, H or J |
| All values in E, B and C correct with working values in correct order at C | A1 (EBC) | Including order of labelling |
| All values F, G and D correct in correct order | A1 (FGD) | F, G and D must be labelled in that order and after A, E, B and C |
| All values in H and J correct (follow through) | A1ft (HJ) | H and J labelled in that order; H labelled after all other nodes excluding J |
| Shortest path: ABGHJ | A1 | CAO |
| Length: 56 (km) | A1ft | Follow through on final value at J |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route from D to H via A: DCBABGH | B1 | CAO |
| Length: 80 (km) | B1ft | Follow through: final value at D + final value at H |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| EF, FG, BG, CB; CD, AE; GH, HJ | M1; A1; A1 | First four arcs (or five nodes EFGBC) correctly chosen in order (M1 max if any rejections seen). First six arcs (all nodes EFGBCDAHJ) correctly chosen in order (c1A1). CSO all arcs correctly stated in correct order with no extras (c2A1) |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Length of MST: 89 (km) | B1 | CAO; condone lack of or incorrect units |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-04_1059_1424_228_317}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Sally wishes to travel from A to J. She wishes to minimise the distance she travels.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to J. State the path and its length.
\item Find a route of minimal length that goes from D to H via A and state its length.
\item Use Prim's algorithm, starting at E , to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
\item Find the length, in kilometres, of your minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q3 [12]}}