| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2022 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Chinese Postman with start/end constraints |
| Difficulty | Challenging +1.2 This is a multi-part Chinese Postman problem with varying start/end constraints. Part (a) is routine Dijkstra's algorithm. Parts (b) and (c) require identifying odd-degree vertices and optimal pairings, which is standard Further Maths D1 content but involves more problem-solving than pure recall. The multiple parts and need to apply the algorithm twice with different constraints elevates it slightly above average difficulty for Further Maths. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| A larger value replaced by a smaller value in at least two different Working Value boxes at either C or F or G or H or J or K | M1 | 1.1b |
| All values at A, B, E, D and C correct. Condone lack of 0 in A's working value | A1 | 1.1b |
| All values at F, H and G correct and working values in correct order | A1 | 1.1b |
| All values at J and K correct on follow through, working values in correct order | A1ft | 1.1b |
| (i) Diagram correct | ||
| (ii) Path from A to K: ABEHGK | A1 | 2.2a |
| (iii) Length of shortest path from A to K is 59 (km) | A1ft | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Repeated edges: AB, BE, EH | B1 | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Length of route \(= 299 + 28 = 327\) (km) | B1ft | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Route must start at A and finish at K, therefore need to consider pairings of nodes D, E, H and K | M1 | 3.1b |
| \(D(AB)E + H(G)K = 26 + 31 = 57\) | A1 | 1.1b |
| \(D(FG)H + E(HG)K = 30 + 47 = 77\) | A1 | 1.1b |
| \(D(FG)K + EH = 49 + 16 = 65\) | A1 | 1.1b |
| Length of new route \(= 299 + 57 = 356\) (km) | A1 | 2.2a |
## Question 2:
### Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| A larger value replaced by a smaller value in at least **two** different Working Value boxes at either C or F or G or H or J or K | M1 | 1.1b |
| All values at A, B, E, D and C correct. Condone lack of 0 in A's working value | A1 | 1.1b |
| All values at F, H and G correct and working values in correct order | A1 | 1.1b |
| All values at J and K correct on follow through, working values in correct order | A1ft | 1.1b |
| **(i)** Diagram correct | | |
| **(ii)** Path from A to K: ABEHGK | A1 | 2.2a |
| **(iii)** Length of shortest path from A to K is 59 (km) | A1ft | 2.2a |
### Part (b)(i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Repeated edges: AB, BE, EH | B1 | 2.2a |
### Part (b)(ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Length of route $= 299 + 28 = 327$ (km) | B1ft | 2.2a |
### Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Route must start at A and finish at K, therefore need to consider pairings of nodes D, E, H and K | M1 | 3.1b |
| $D(AB)E + H(G)K = 26 + 31 = 57$ | A1 | 1.1b |
| $D(FG)H + E(HG)K = 30 + 47 = 77$ | A1 | 1.1b |
| $D(FG)K + EH = 49 + 16 = 65$ | A1 | 1.1b |
| Length of new route $= 299 + 57 = 356$ (km) | A1 | 2.2a |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-03_563_1445_214_312}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
[The total weight of the network is 299]
Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track.
One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm to find the shortest path from A to K .
\item State the length of the shortest path from A to K .\\
(6)
The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E .
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item State the edges that will need to be traversed twice.
\item Find the length of Blanche's route.
It is now decided to start the inspection route at A and finish at K . Blanche must minimise the length of her route and travel along each track at least once.
\end{enumerate}\item By considering the pairings of all relevant nodes, find the length of Blanche's new route. You must make your method and working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2022 Q2 [13]}}