| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2019 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Multiple paths of same minimum weight |
| Difficulty | Challenging +1.2 This is a multi-part Further Maths Decision question requiring Dijkstra's algorithm and Chinese Postman concepts. Part (a) involves systematic application of Dijkstra's with algebraic weights and solving simultaneous equations from the constraint that three paths have equal minimum length—this requires careful bookkeeping but is methodical. Parts (b-d) are routine applications of Chinese Postman theory once the network is understood. The algebraic element and need to identify three equal-length paths elevates this above a standard algorithm application, but it remains a structured problem following established procedures rather than requiring novel insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| 4(a) | Attempt to form a pair of simultaneous equations using their three |
| Answer | Marks |
|---|---|
| x=3,y =6 | M1 |
| Answer | Marks |
|---|---|
| A1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| (b) | Arcs BC and CD need to be traversed twice | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| (c) | Vertex C would appear 4 times | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| (d) | 135 + 4(3) + 2(6) + 12 = 171 | B1ft |
| Answer | Marks | Guidance |
|---|---|---|
| Question | Scheme | Marks |
Question 4:
--- 4(a) ---
4(a) | Attempt to form a pair of simultaneous equations using their three
working values from H
e.g. 3x+ y =15 or x+ y =9
x=3,y =6 | M1
A1
A1ft
A1
M1dep
A1
A1 | 1.1b
1.1b
1.1b
1.1b
3.1a
2.1
2.2a
(7)
(b) | Arcs BC and CD need to be traversed twice | B1 | 1.1b
(1)
(c) | Vertex C would appear 4 times | B1 | 2.2a
(1)
(d) | 135 + 4(3) + 2(6) + 12 = 171 | B1ft | 1.1b
(1)
(10 marks)
Notes
(a)
M1: For a larger number replaced by a smaller one in the working value boxes at C, F or G
A1: For all values correct (and in correct order) at A, D, B and C (condone order of labelling starting
at A with 0)
A1ft: For all values correct (and in correct order) at G and F following through from A, D, B and C
A1: For all working values correct at E and H (order of working values must be correct at E but
condone any order of working values at H) however, at H if only one working value is seen e.g. 18
+ 3x + y then both 33 and 24 + x + y must be seen (or clearly implied) in later working for this
mark to be awarded (e.g. 3x + y = 15 and x + y = 9 would imply this). Similarly, if only two
working values seen (e.g. 18 + 3x + y and 33) at H then the third (24 + x + y) must be implied
by later working. Any incorrect working values seen at H though will score A0
M1dep: Forming two equations from the candidate’s three working values at H
(so two of their 18+3x+ y =24+x+ y, 18+3x+ y =33 and 24+x+ y =33) – allow all three
working values stated anywhere in their solution – dependent on previous M mark. Must be a
complete method – so for those finding x from18+3x+ y =24+x+ ythey must also either state or
use one of the other two equations (so candidates must be interacting with all three paths from A to
H)
A1: Two correct equations formed (dependent on correct working values either seen at H or in their
subsequent working) – can be unsimplified but must come from correct working
A1: CAO for x and y (x = 3 and y = 6) – must come from correct working
If all three correct working values at H are seen (either at H or subsequent working) together with
both correct answers (with no other working) then award M1A1A1.
(b)
B1: CAO (arcs BC and CD)
(c)
B1: CAO (4 times)
(d)
B1ft: Follow through only for 135 + 12 + 4x + 2y (for their x and y values provided 7< x+ y<20
and x and y are positive constants)
Question | Scheme | Marks | AOs\includegraphics{figure_1}
**Figure 1**
[The total weight of the network is $135 + 4x + 2y$]
The weights on the arcs in Figure 1 represent distances. The weights on the arcs CE and GH are given in terms of $x$ and $y$, where $x$ and $y$ are positive constants and $7 < x + y < 20$
There are three paths from A to H that have the same minimum length.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find $x$ and $y$. [7]
\end{enumerate}
An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item State the arcs that are traversed twice. [1]
\item State the number of times that vertex C appears in the inspection route. [1]
\item Determine the length of the inspection route. [1]
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2019 Q4 [10]}}