Edexcel FD2 2019 June — Question 3 13 marks

Exam BoardEdexcel
ModuleFD2 (Further Decision 2)
Year2019
SessionJune
Marks13
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeDynamic programming shortest/longest path
DifficultyChallenging +1.2 This is a standard Further Maths D2 dynamic programming question requiring systematic application of the algorithm to find optimal paths and then using inequalities to determine the range of x. While it requires careful bookkeeping across multiple stages and comparing path weights, the technique is algorithmic and well-practiced in FD2. The constraint that the optimal path passes through B provides clear direction for setting up inequalities, making this moderately above average difficulty but not requiring novel insight.
Spec7.04a Shortest path: Dijkstra's algorithm7.04f Network problems: choosing appropriate algorithm
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5274a614-7862-49f0-ad1d-b59b73aa51ad-04_1047_1691_210_187} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} In Figure 1 the weight of \(\operatorname { arc } \mathrm { SB }\) is denoted by \(x\) where \(x \geqslant 0\)
  1. Explain why Dijkstra's algorithm cannot be used on the directed network in Figure 1.
    (1) It is given that the minimum weight route from S to T passes through B .
  2. Use dynamic programming to find
    1. the range of possible values of \(x\)
    2. the minimum weight route from S to T .
      (12)
Question 3:
Part (a)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Dijkstra's algorithm cannot be used on a network with negative weights1B1 Do not accept "cannot be used on a directed network". Condone references to "negative edges"
Part (b)(i)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Stage 0 correct: \(GT=28^*,\ HT=19^*,\ IT=-24^*,\ JT=17^*\)1B1 Stage 0 correct
Stage 1 with 3 states, 7 rows: \(DG=-24+28=4^*\), \(DH=18+19=37\), \(EH=24+19=43\), \(EI=27-24=3^*\), \(FG=-25+28=3\), \(FI=14-24=-10\), \(FJ=-30+17=-13^*\)1M1, 1A1, 2A1 1M1: Stage 1 completed with \(\geq 7\) rows. 1A1: any two states correct. 2A1: CAO all 3 states (must be 7 rows, no extras)
Stage 2 with 3 states, \(\geq 6\) rows: \(AD=32+4=36\), \(AE=29+3=32^*\), \(BD=20+4=24\), \(BE=19+3=22\), \(BF=-17-13=-30^*\), \(CF=13-13=0^*\)2M1, 3A1ft, 4A1 2M1: Stage 2 completed with \(\geq 6\) rows. 3A1ft: any 2 states correct. 4A1: CAO all 3 states (no extra rows)
Stage 3 with 1 state, \(\geq 3\) rows: \(SA=13+32=45\), \(SB=x-30\), \(SC=24+0=24\)3M1, 5A1ft 3M1: Stage 3 completed with \(\geq 3\) rows. 5A1ft: CAO for Stage 3 following their optimal values
\(x-30<24 \Rightarrow (0\leq)\ x<54\)4dM1, 6A1 4dM1: dependent on 3M1 and \(\geq 1\) of first two M marks. Correct inequality using SB and least of SA, SC. 6A1: CSO, strict inequality required
Part (b)(ii)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Route: \(S-B-F-J-T\)1dB1 Correct route. Dependent on 3rd method mark 
# Question 3:

## Part (a)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm cannot be used on a network with negative weights | 1B1 | Do not accept "cannot be used on a directed network". Condone references to "negative edges" |

## Part (b)(i)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Stage 0 correct: $GT=28^*,\ HT=19^*,\ IT=-24^*,\ JT=17^*$ | 1B1 | Stage 0 correct |
| Stage 1 with 3 states, 7 rows: $DG=-24+28=4^*$, $DH=18+19=37$, $EH=24+19=43$, $EI=27-24=3^*$, $FG=-25+28=3$, $FI=14-24=-10$, $FJ=-30+17=-13^*$ | 1M1, 1A1, 2A1 | 1M1: Stage 1 completed with $\geq 7$ rows. 1A1: any two states correct. 2A1: CAO all 3 states (must be 7 rows, no extras) |
| Stage 2 with 3 states, $\geq 6$ rows: $AD=32+4=36$, $AE=29+3=32^*$, $BD=20+4=24$, $BE=19+3=22$, $BF=-17-13=-30^*$, $CF=13-13=0^*$ | 2M1, 3A1ft, 4A1 | 2M1: Stage 2 completed with $\geq 6$ rows. 3A1ft: any 2 states correct. 4A1: CAO all 3 states (no extra rows) |
| Stage 3 with 1 state, $\geq 3$ rows: $SA=13+32=45$, $SB=x-30$, $SC=24+0=24$ | 3M1, 5A1ft | 3M1: Stage 3 completed with $\geq 3$ rows. 5A1ft: CAO for Stage 3 following their optimal values |
| $x-30<24 \Rightarrow (0\leq)\ x<54$ | 4dM1, 6A1 | 4dM1: dependent on 3M1 and $\geq 1$ of first two M marks. Correct inequality using SB and least of SA, SC. 6A1: CSO, strict inequality required |

## Part (b)(ii)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Route: $S-B-F-J-T$ | 1dB1 | Correct route. Dependent on 3rd method mark |

---
3.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{5274a614-7862-49f0-ad1d-b59b73aa51ad-04_1047_1691_210_187}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

In Figure 1 the weight of $\operatorname { arc } \mathrm { SB }$ is denoted by $x$ where $x \geqslant 0$
\begin{enumerate}[label=(\alph*)]
\item Explain why Dijkstra's algorithm cannot be used on the directed network in Figure 1.\\
(1)

It is given that the minimum weight route from S to T passes through B .
\item Use dynamic programming to find
\begin{enumerate}[label=(\roman*)]
\item the range of possible values of $x$
\item the minimum weight route from S to T .\\
(12)
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{Edexcel FD2 2019 Q3 [13]}}
This paper (6 questions)
View full paper
Q1 10 Q2 7 Q3 13 Q4 14 Q5 11 Q6 8