| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2023 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Standard +0.3 This is a straightforward application of two standard algorithms (Dijkstra and Prim) with minimal conceptual challenge. Part (a) requires basic understanding that running Dijkstra from C finds shortest paths to both A and J. Parts (b-d) are routine algorithmic execution that Further Maths students practice extensively. The 'via C' constraint is handled trivially by the algorithm choice rather than requiring problem-solving insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Dijkstra's algorithm only finds the shortest path from a given starting node to all other nodes. If the shortest route from A to J via C is required, this is equivalent to finding shortest paths from C to A and C to J, so as C is common to both paths the algorithm should start at C | B1 | Must recognise limitation that algorithm finds shortest path from one given start node to all others. Must clearly indicate C is the starting vertex. Must state this way round (C to J and C to A) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A larger working value being replaced by a smaller working value at any two of A, B, E, F, G, J | M1 | |
| All values at C, D, B and H correct with working values in correct order | A1 | |
| All values at G, E and A correct with working values in correct order | A1 | Penalise order of labelling once per question. Condone additional working value of 57 after 39 (but A0 if 57 appears before 41 or 39 at G) |
| All values in F and J correct on follow through, working values in correct order | A1ft | To follow through F: check working values follow from candidate's final values for nodes directly attached to F (B, E, G, J) |
| Shortest route from A to J via C is \(A\ B\ D\ C\ D\ G\ E\ F\ J\) | A1 | cao — must be stated from A to J |
| Shortest length: \(70 + 86 = 156\) (km) | A1ft | Follow through their final value at A + their final value at J only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Prim's algorithm from C: CD, BD, DG, EG, GH, EF, FJ, AB | M1 | First three arcs (CD, BD, DG) correctly chosen, or first four nodes (C, D, B, G) correctly chosen in order. If any explicit rejections seen M1 max only. List of weights alone scores M0 |
| First six arcs correctly chosen in order (CD, BD, DG, EG, GH, EF) or all nodes correctly chosen in order (C, D, B, G, E, H, F, J, A) | A1 | |
| All arcs correctly stated and chosen in correct order, no additional/incorrect/repeated arcs | A1 | cso |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| 155 (km) | B1 | cao (no units required) — must follow from correct arcs in (c) |
## Question 3:
### Part 3(a):
| Answer | Mark | Guidance |
|--------|------|----------|
| Dijkstra's algorithm only finds the shortest path from a given starting node to all other nodes. If the shortest route from A to J via C is required, this is equivalent to finding shortest paths from C to A and C to J, so as C is common to both paths the algorithm should start at C | B1 | Must recognise limitation that algorithm finds shortest path from one given start node to all others. Must clearly indicate C is the starting vertex. Must state this way round (C to J and C to A) |
**Total: (1 mark)**
### Part 3(b):
| Answer | Mark | Guidance |
|--------|------|----------|
| A larger working value being replaced by a smaller working value at any two of A, B, E, F, G, J | M1 | |
| All values at C, D, B and H correct with working values in correct order | A1 | |
| All values at G, E and A correct with working values in correct order | A1 | Penalise order of labelling once per question. Condone additional working value of 57 after 39 (but A0 if 57 appears before 41 or 39 at G) |
| All values in F and J correct on follow through, working values in correct order | A1ft | To follow through F: check working values follow from candidate's final values for nodes directly attached to F (B, E, G, J) |
| Shortest route from A to J via C is $A\ B\ D\ C\ D\ G\ E\ F\ J$ | A1 | cao — must be stated from A to J |
| Shortest length: $70 + 86 = 156$ (km) | A1ft | Follow through their final value at A + their final value at J only |
**Total: (6 marks)**
### Part 3(c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Prim's algorithm from C: CD, BD, DG, EG, GH, EF, FJ, AB | M1 | First three arcs (CD, BD, DG) correctly chosen, or first four nodes (C, D, B, G) correctly chosen in order. If any explicit rejections seen M1 max only. List of weights alone scores M0 |
| First six arcs correctly chosen in order (CD, BD, DG, EG, GH, EF) or all nodes correctly chosen in order (C, D, B, G, E, H, F, J, A) | A1 | |
| All arcs correctly stated and chosen in correct order, no additional/incorrect/repeated arcs | A1 | cso |
**Note — Misread:** Starting at node other than C scores M1 only if first three arcs (or four nodes) correct and in correct order.
**Total: (3 marks)**
### Part 3(d):
| Answer | Mark | Guidance |
|--------|------|----------|
| 155 (km) | B1 | cao (no units required) — must follow from correct arcs in (c) |
**Total: (1 mark)**3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{9edb5209-4244-4916-b3ee-d77e395e8cab-04_977_1472_259_294}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track.\\
Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel.
Given that Dijkstra's algorithm is to be applied only once to find Dyfan's route,
\begin{enumerate}[label=(\alph*)]
\item explain why the algorithm should begin at C.
\item Use Dijkstra's algorithm to find the shortest route from A to J via C. State this route and its length.
\item Use Prim's algorithm, starting at C , 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 State the total length, in km , of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2023 Q3 [11]}}