Edexcel D1 2013 June — Question 7 7 marks

Exam BoardEdexcel
ModuleD1 (Decision Mathematics 1)
Year2013
SessionJune
Marks7
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicShortest Path
TypeBasic Dijkstra's algorithm application
DifficultyModerate -0.8 This is a straightforward application of Dijkstra's algorithm with a minor twist (choosing the starting vertex). The algorithm itself is mechanical and routine for D1 students, requiring no problem-solving insight beyond recognizing that starting from J finds both paths simultaneously. The 7-mark allocation reflects standard bookwork rather than conceptual challenge.
Spec7.04a Shortest path: Dijkstra's algorithm
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-08_748_1563_251_242} \captionsetup{labelformat=empty} \caption{Figure 5}
\end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\). A route of minimum length is required. It is decided to use Dijkstra's algorithm to find the shortest routes between \(\mathrm { C } _ { 1 }\) and J and between \(\mathrm { C } _ { 2 }\) and J .
  1. Explain why J , rather than \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\), should be chosen as the starting vertex.
    (1)
  2. Use Dijkstra's algorithm to find the shortest route needed to transport the crane. State your route and its length.
    (6)
Question 7 Notes:
- a1B1: CAO
- b1M1: A larger value replaced by a smaller value at least once in the working values at either G, E, D, \(C_1\) or \(C_2\)
- b1A1: All values in G, H, I and J correct. The working values at G must be in the correct order. Condone lack of 0 in the working value at J
- b2A1: All values in D, E and F correct and the working values in the correct order. Penalise order of labelling only once per question. (F, E and D labelled in that order with G, H, I and J labelled before F)
- b3A1 ft: All values in \(C_1\) and \(C_2\) ft correct and the working values in the correct order. Penalise order of labelling only once per question. (\(C_2\) labelled after all other nodes (D to J) – condone lack of final value for \(C_1\))
- b4A1: Route CAO
- b5A1 ft: Their final value ft (if answer is not 48 ft their final value at either \(C_1\) or \(C_2\) dependent on their route)
If the candidate uses either \(C_1\) or \(C_2\) as the starting vertex then this is not a misread. They can score a maximum of M1A0A0A0A1A1 ft. If starting at:
- \(C_1\) – M1 for a larger value replaced by a smaller value at either \(C_2\), F, G, H, I or J, then A0 A0 A0 then A1 for the route (\(C_1\)DFGIJ) and then A1 for 49 (or ft their final value at J)
- \(C_2\) – M1 for a larger value replaced by a smaller value at either \(C_1\), F, G, H, I or J, then A0 A0 A0 then A1 for the route (\(C_2\) EFGIJ) and then A1 for 48 (or ft their final value at J)
If the candidate uses both \(C_1\) and \(C_2\) as the starting vertices then award M1 for a larger value replaced by a smaller value at either F, G, H, I or J, then A0 A0 then A1 for the correct route only (\(C_2\)EFGIJ) and A1 for 48 (no ft).
**Question 7 Notes:**
- a1B1: CAO
- b1M1: A larger value replaced by a smaller value at least once in the working values at either G, E, D, $C_1$ or $C_2$
- b1A1: All values in G, H, I and J correct. The working values at G must be in the correct order. Condone lack of 0 in the working value at J
- b2A1: All values in D, E and F correct and the working values in the correct order. Penalise order of labelling only once per question. (F, E and D labelled in that order with G, H, I and J labelled before F)
- b3A1 ft: All values in $C_1$ and $C_2$ ft correct and the working values in the correct order. Penalise order of labelling only once per question. ($C_2$ labelled after all other nodes (D to J) – condone lack of final value for $C_1$)
- b4A1: Route CAO
- b5A1 ft: Their final value ft (if answer is not 48 ft their final value at either $C_1$ or $C_2$ dependent on their route)

If the candidate uses either $C_1$ or $C_2$ as the starting vertex then this is not a misread. They can score a maximum of M1A0A0A0A1A1 ft. If starting at:
- $C_1$ – M1 for a larger value replaced by a smaller value at either $C_2$, F, G, H, I or J, then A0 A0 A0 then A1 for the route ($C_1$DFGIJ) and then A1 for 49 (or ft their final value at J)
- $C_2$ – M1 for a larger value replaced by a smaller value at either $C_1$, F, G, H, I or J, then A0 A0 A0 then A1 for the route ($C_2$ EFGIJ) and then A1 for 48 (or ft their final value at J)

If the candidate uses both $C_1$ and $C_2$ as the starting vertices then award M1 for a larger value replaced by a smaller value at either F, G, H, I or J, then A0 A0 then A1 for the correct route only ($C_2$EFGIJ) and A1 for 48 (no ft).
7.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-08_748_1563_251_242}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}

Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either $\mathrm { C } _ { 1 }$ or $\mathrm { C } _ { 2 }$. A route of minimum length is required.

It is decided to use Dijkstra's algorithm to find the shortest routes between $\mathrm { C } _ { 1 }$ and J and between $\mathrm { C } _ { 2 }$ and J .
\begin{enumerate}[label=(\alph*)]
\item Explain why J , rather than $\mathrm { C } _ { 1 }$ or $\mathrm { C } _ { 2 }$, should be chosen as the starting vertex.\\
(1)
\item Use Dijkstra's algorithm to find the shortest route needed to transport the crane. State your route and its length.\\
(6)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2013 Q7 [7]}}
This paper (8 questions)
View full paper
Q1 7 Q2 8 Q3 12 Q4 8 Q5 10 Q6 7 Q7 7 Q8 16