| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2019 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Chinese Postman with start/end constraints |
| Difficulty | Standard +0.3 This is a standard Chinese Postman problem with straightforward modifications. Part (a) is routine Dijkstra's algorithm application. Parts (b)-(c) require identifying odd vertices and pairing them for the Chinese Postman algorithm with fixed start/end points—a textbook Further Maths procedure. Part (d) involves removing edges and re-analyzing, but the logic (checking vertex degrees, pairing odd vertices) remains algorithmic. While multi-part and requiring careful bookkeeping, it demands no novel insight beyond applying learned algorithms methodically. |
| 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 working boxes at C or D or E or G or J | M1 | 1.1b |
| All values in A, B, F and E correct | A1 | 1.1b |
| All values G, C and J correct with working values in correct order | A1 | 1.1b |
| All values in H and D correct on follow through, working values in correct order | A1ft | 1.1b |
| Path from A to D is AFGJD | A1 | 2.2a |
| Length of path from A to D is 78 metres | A1ft | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct three pairings of the four odd nodes (A, C, E and H) | M1 | 3.1b |
| \(A(FG)C + E(J)H = 61 + 23 = 84\); any row correct including pairing and total | A1ft | 1.1b |
| \(A(B)E + C(GJ)H = 53 + 27 = 80^*\); \(A(FGJ)H + C(G)E = 74 + 17 = 91\); all three rows correct | A1 | 1.1b |
| Repeat arcs: AB, BE, CG, GJ and JH | A1 | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Length of route is \(370 + 80 = 450\) metres | B1ft | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| If node B is removed this makes D, C, G and H odd | M1 | 3.1b |
| Shortest path between any two odd nodes is CG (so repeat CG), route should start at D and finish at H (or vice-versa) | A1 | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Length of new route is \(370 - 38 - 42 - 15 + 7 = 282\) metres | B1 | 2.2a |
# Question 2:
## Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| A larger value replaced by a smaller value in at least two working boxes at C or D or E or G or J | M1 | 1.1b |
| All values in A, B, F and E correct | A1 | 1.1b |
| All values G, C and J correct with working values in correct order | A1 | 1.1b |
| All values in H and D correct on follow through, working values in correct order | A1ft | 1.1b |
| Path from A to D is AFGJD | A1 | 2.2a |
| Length of path from A to D is 78 metres | A1ft | 2.2a |
## Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct three pairings of the four odd nodes (A, C, E and H) | M1 | 3.1b |
| $A(FG)C + E(J)H = 61 + 23 = 84$; any row correct including pairing and total | A1ft | 1.1b |
| $A(B)E + C(GJ)H = 53 + 27 = 80^*$; $A(FGJ)H + C(G)E = 74 + 17 = 91$; all three rows correct | A1 | 1.1b |
| Repeat arcs: AB, BE, CG, GJ and JH | A1 | 2.2a |
## Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Length of route is $370 + 80 = 450$ metres | B1ft | 2.2a |
## Part (d)(i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| If node B is removed this makes D, C, G and H odd | M1 | 3.1b |
| Shortest path between any two odd nodes is CG (so repeat CG), route should start at D and finish at H (or vice-versa) | A1 | 2.2a |
## Part (d)(ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Length of new route is $370 - 38 - 42 - 15 + 7 = 282$ metres | B1 | 2.2a |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{162f9d72-84a4-4b1a-93cf-b7eeb7f957ae-03_663_1421_203_322}
\captionsetup{labelformat=empty}
\caption{Figure 1\\[0pt]
[The total weight of the network is 370]}
\end{center}
\end{figure}
Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to D, stating the path and its length.
On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G .
\item Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
\item Find the length of Naasir's route.
On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B .
\item \begin{enumerate}[label=(\roman*)]
\item Determine the possible starting and finishing points so that the length of Naasir's route is minimised. You must give reasons for your answer.
\item Find the length of Naasir's new route.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2019 Q2 [14]}}