| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2021 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Incomplete Dijkstra reconstruction |
| Difficulty | Challenging +1.2 This is a multi-part Dijkstra's algorithm question requiring reconstruction of arc weights from given information. Parts (a)-(c) involve reading results from a partially completed algorithm (routine). Part (d) requires setting up and solving simultaneous equations using MST and shortest path constraints, which is moderately challenging but follows standard Further Maths problem-solving patterns. The question is harder than typical A-level due to the reverse-engineering aspect, but remains accessible with systematic working. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(66\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Arcs and weights listed correctly (first set) | B1 | |
| Arcs and weights listed correctly (second set) | B1 | |
| Arcs and weights listed correctly (third set) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Shortest path from A to G: ABCFG | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Prim's algorithm gives: \(25+10+7+CE+EF+3=80\) | M1 | |
| Shortest path from A to F via E is ABEF: \(56+EF=67\) | M1 | |
| \(EF=11\) and \(CE=24\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| cao | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(AB\), \(AC\) and \(AD\) correct | B1 | |
| Any other four arcs correct | B1 | |
| All correct | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| cao | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Use given information regarding Prim's algorithm to set up an equation for \(CE\) and \(EF\) using the weight of the correct arcs from (b) so \(AB + BC + CD + CE + EF + FG = 80\) | M1 | |
| Use given information regarding shortest path from \(A\) to \(F\) via \(E\) (using the path \(ABEF\)) to get an equation for \(EF\) \((AB + BE + EF = 67)\) | M1 | This mark can be awarded for correctly stating \(EF\) as \(11\) |
| cao for both \(CE\) and \(EF\) | A1 |
# Question 4:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| $66$ | B1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Arcs and weights listed correctly (first set) | B1 | |
| Arcs and weights listed correctly (second set) | B1 | |
| Arcs and weights listed correctly (third set) | B1 | |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Shortest path from A to G: ABCFG | B1 | |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Prim's algorithm gives: $25+10+7+CE+EF+3=80$ | M1 | |
| Shortest path from A to F via E is ABEF: $56+EF=67$ | M1 | |
| $EF=11$ and $CE=24$ | A1 | |
# Question (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| cao | **B1** | |
# Question (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| $AB$, $AC$ and $AD$ correct | **B1** | |
| Any other four arcs correct | **B1** | |
| All correct | **B1** | |
# Question (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| cao | **B1** | |
# Question (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| Use given information regarding Prim's algorithm to set up an equation for $CE$ and $EF$ using the weight of the correct arcs from (b) so $AB + BC + CD + CE + EF + FG = 80$ | **M1** | |
| Use given information regarding shortest path from $A$ to $F$ via $E$ (using the path $ABEF$) to get an equation for $EF$ $(AB + BE + EF = 67)$ | **M1** | This mark can be awarded for correctly stating $EF$ as $11$ |
| cao for both $CE$ and $EF$ | **A1** | |4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{d3f5dcb4-3e23-4d78-965a-a1acaac13819-05_712_1433_223_315}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Dijkstra's algorithm has been applied to the network in Figure 2.\\
A working value has only been replaced at a node if the new working value is smaller.
\begin{enumerate}[label=(\alph*)]
\item State the length of the shortest path from A to G .
\item Complete the table in the answer book giving the weight of each arc listed. (Note that arc CE and arc EF are not in the table.)
\item State the shortest path from A to G.
It is now given that
\begin{itemize}
\item when Prim's algorithm, starting from A, is applied to the network, the order in which the arcs are added to the tree is $\mathrm { AB } , \mathrm { BC } , \mathrm { CD } , \mathrm { CE } , \mathrm { EF }$ and FG
\item the weight of the corresponding minimum spanning tree is 80
\item the shortest path from A to F via E has weight 67
\item Determine the weight of arc CE and the weight of arc EF , making your reasoning clear.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2021 Q4 [8]}}