| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Easy -1.2 This is a straightforward application of Dijkstra's algorithm, a standard D1 topic requiring only mechanical execution of a learned procedure on a given network. Part (a) is routine algorithmic work, part (b) tests basic understanding of reading the algorithm's output, and part (c) requires simple observation from the completed diagram. No problem-solving insight or novel thinking is needed—purely procedural recall below average difficulty. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: SBEFHT<br>Time: 87 minutes | M1 A1 A1ft A1 | M1: Smaller number replacing larger number in the working values at C or D or G or H or T. (generous – give bod)<br>1A1: All values in boxes S, A, B, E and F correct<br>2A1ft: All values in boxes C and D (ft) correct. Penalise order of labelling errors just once.<br>3A1: All values in boxes G, H and T correct<br>1B1: CAO (not ft)<br>2B1ft: Follow through from their T value, condone lack of units here. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Accept demonstration of relevant subtractions, or general explanation. | B2ft, 1ft, 0 | 1B1ft: Partially complete account, maybe muddled, bod gets B1<br>2B1ft: Complete, clear account. |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: EFHT | B1 | 1B1: CAO |
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: SBEFHT<br>Time: 87 minutes | M1 A1 A1ft A1 | M1: Smaller number replacing larger number in the working values at C or D or G or H or T. (generous – give bod)<br>1A1: All values in boxes S, A, B, E and F correct<br>2A1ft: All values in boxes C and D (ft) correct. Penalise order of labelling errors just once.<br>3A1: All values in boxes G, H and T correct<br>1B1: CAO (not ft)<br>2B1ft: Follow through from their T value, condone lack of units here. |
**Total: 6 marks**
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Accept demonstration of relevant subtractions, or general explanation. | B2ft, 1ft, 0 | 1B1ft: Partially complete account, maybe muddled, bod gets B1<br>2B1ft: Complete, clear account. |
**Total: 2 marks**
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: EFHT | B1 | 1B1: CAO |
**Total: 1 mark**
**Grand Total for Q6: 9 marks**
---\includegraphics{figure_5}
Figure 5 shows a network of cycle tracks within a national park. The number on each arc represents the time taken, in minutes, to cycle along the corresponding track.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the quickest route from S to T. State your quickest route and the time it takes.
[6]
\item Explain how you determined your quickest route from your labelled diagram.
[2]
\item Write down the quickest route from E to T.
[1]
\end{enumerate}
(Total 9 marks)
\hfill \mbox{\textit{Edexcel D1 2010 Q6 [9]}}