Edexcel D1 2021 June — Question 5 10 marks

Exam BoardEdexcel
ModuleD1 (Decision Mathematics 1)
Year2021
SessionJune
Marks10
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicShortest Path
TypeDijkstra with route via intermediate vertex
DifficultyModerate -0.3 This is a straightforward application of Dijkstra's algorithm with standard bookwork. Part (a) is trivial (start at A), part (b) is routine algorithm execution, and part (c) simply requires adding two shortest paths together. The question involves no novel problem-solving or insight beyond textbook procedures, making it slightly easier than average for A-level.
Spec7.04a Shortest path: Dijkstra's algorithm
5. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{44ddb176-e265-4545-b438-c1b5ffb40852-06_965_1290_237_390} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Tamasi, who lives at A, needs to collect a caravan. Tamasi can collect a caravan from either J or K. Tamasi decides to use Dijkstra's algorithm once to find the shortest routes between A and J and between A and K.
  1. State, with a reason, which vertex should be chosen as the starting vertex for the algorithm.
  2. Use Dijkstra's algorithm to find the shortest routes from A to J and from A to K . You should state the routes and their corresponding lengths. Tamasi's brother lives at F . He needs to visit Tamasi at A and then visit their mother who lives at H .
  3. Find a route of minimal length that goes from F to H via A .
(a) B1
Start at A – e.g. we would be able to find the shortest distance from A to every other vertex or e.g. A appears in both required routes
B1dep (2)
Correct reason for starting at A (dependent on first B mark) – either need to explicitly mention that A appears on both routes or if starting at A then the shortest route to all other vertices (or just to vertices J and K) can be found
(b) M1
Any larger working value replaced by any smaller working value at any two nodes except A and C (for example, if correct at B, 32 is replaced by 31 which is a larger value being replaced by a smaller value at one node – as this is a method mark the values do not need to be correct)
A1
All values at A, C, D, B and G correct and the working values in the correct order (including order of labelling so nodes must be labelled in the order A, then C, then D, then B, then G). Condone lack of a zero as a working value at A
A1
All values at E, F and H correct and the working values in the correct order. Penalise order of labelling only once per question (so E, F and H must be labelled in that order and E must be labelled after A, C, D, B and G)
A1ft
All values in J and K correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through J check that the working values at J follow from the candidate's final values for the nodes that are directly attached to J (which are A, F and G). For example, if correct then the order of labelling of nodes A, F and G is 1, 7 and 5 respectively so the working values at J should come from A, G and F in that order. The first working value at J should be 0 (the final value at A) + 84 (the weight of the arc AJ), the second working value at J should be 40 (the final value at G) + 42 (the weight of the arc GJ) and the final working value at J should be 48 (the final value at F) + 32 (the weight of the arc FJ). Repeat the process for K (which will have working values from D, G and H with the order of these nodes determined by the candidate's order of labelling at D, G and H)
A1
One correct route (either ACDGFJ or ACDBEHK) – allow if reversed (e.g. JFGDCA) and allow if stated in terms of arcs (e.g. AC, CD, DG, GF, FJ)
A1
Both routes correct (as above – routes can be reversed and accept in terms of arcs)
A1ft (7)
Both lengths correct following through their final values at J and K. Condone correct answers or correct answers following through their diagram even if not explicitly clear which value refers to which path
(c) B1 (1)
Correct answer only (FGDCACDBEH or FG, GD, DC, CA, AC, CD, DB, BE, EH) – if stated in terms of arcs then arcs AC and CD must appear twice in their route
If Dijkstra is completed twice (from J and K) then full marks can be awarded. If the candidate uses just J or K as the starting vertex in (b) then this is not a misread. The candidate can score if starting at J: M1 (as above), A1 (for correct values at J, F, G, B, D), A0, A0, A1 (for route JFGDCA), A1 (for length 80), A0 so 4 out of 7 max. If starting at K: M1 (as above), A1 (for correct values at K, H, E, G, B), A0, A0, A1 (for route KHEBDCA), A1 (for length 81), A0 so 4 out of 7 max.
**(a)** B1
Start at A – e.g. we would be able to find the shortest distance from A to every other vertex or e.g. A appears in both required routes

B1dep (2)
Correct reason for starting at A (dependent on first B mark) – either need to explicitly mention that A appears on both routes or if starting at A then the shortest route to all other vertices (or just to vertices J and K) can be found

**(b)** M1
Any larger working value replaced by any smaller working value at any two nodes except A and C (for example, if correct at B, 32 is replaced by 31 which is a larger value being replaced by a smaller value at one node – as this is a method mark the values do not need to be correct)

A1
All values at A, C, D, B and G correct and the working values in the correct order (including order of labelling so nodes must be labelled in the order A, then C, then D, then B, then G). Condone lack of a zero as a working value at A

A1
All values at E, F and H correct and the working values in the correct order. Penalise order of labelling only once per question (so E, F and H must be labelled in that order and E must be labelled after A, C, D, B and G)

A1ft
All values in J and K correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question. To follow through J check that the working values at J follow from the candidate's final values for the nodes that are directly attached to J (which are A, F and G). For example, if correct then the order of labelling of nodes A, F and G is 1, 7 and 5 respectively so the working values at J should come from A, G and F in that order. The first working value at J should be 0 (the final value at A) + 84 (the weight of the arc AJ), the second working value at J should be 40 (the final value at G) + 42 (the weight of the arc GJ) and the final working value at J should be 48 (the final value at F) + 32 (the weight of the arc FJ). Repeat the process for K (which will have working values from D, G and H with the order of these nodes determined by the candidate's order of labelling at D, G and H)

A1
One correct route (either ACDGFJ or ACDBEHK) – allow if reversed (e.g. JFGDCA) and allow if stated in terms of arcs (e.g. AC, CD, DG, GF, FJ)

A1
Both routes correct (as above – routes can be reversed and accept in terms of arcs)

A1ft (7)
Both lengths correct following through their final values at J and K. Condone correct answers or correct answers following through their diagram even if not explicitly clear which value refers to which path

**(c)** B1 (1)
Correct answer only (FGDCACDBEH or FG, GD, DC, CA, AC, CD, DB, BE, EH) – if stated in terms of arcs then arcs AC and CD must appear twice in their route

**If Dijkstra is completed twice (from J and K) then full marks can be awarded. If the candidate uses just J or K as the starting vertex in (b) then this is not a misread. The candidate can score if starting at J: M1 (as above), A1 (for correct values at J, F, G, B, D), A0, A0, A1 (for route JFGDCA), A1 (for length 80), A0 so 4 out of 7 max. If starting at K: M1 (as above), A1 (for correct values at K, H, E, G, B), A0, A0, A1 (for route KHEBDCA), A1 (for length 81), A0 so 4 out of 7 max.**

---
5.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{44ddb176-e265-4545-b438-c1b5ffb40852-06_965_1290_237_390}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}

Figure 4 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Tamasi, who lives at A, needs to collect a caravan. Tamasi can collect a caravan from either J or K.

Tamasi decides to use Dijkstra's algorithm once to find the shortest routes between A and J and between A and K.
\begin{enumerate}[label=(\alph*)]
\item State, with a reason, which vertex should be chosen as the starting vertex for the algorithm.
\item Use Dijkstra's algorithm to find the shortest routes from A to J and from A to K . You should state the routes and their corresponding lengths.

Tamasi's brother lives at F . He needs to visit Tamasi at A and then visit their mother who lives at H .
\item Find a route of minimal length that goes from F to H via A .
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2021 Q5 [10]}}
This paper (7 questions)
View full paper
Q1 12 Q2 10 Q3 6 Q4 13 Q5 10 Q6 9 Q17