| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | Specimen |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Easy -1.3 This is a straightforward application of Dijkstra's algorithm with a small network, requiring only mechanical execution of a standard procedure taught in D1. The follow-up parts (b) and (c) involve simple reading from the completed diagram rather than additional problem-solving, making this easier than average A-level questions which typically require more conceptual understanding or multi-step reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Smaller number replacing larger number at C, D, G, H or T | M1 | Method mark for Dijkstra's algorithm |
| All values in boxes S, A, B, E and F correct | A1 | CAO |
| All values in boxes C and D correct | A1ft | Penalise order of labelling errors just once |
| All values in boxes G, H and T correct | A1 | CAO |
| Route: SBEFHT | B1 | CAO (not ft) |
| Time: 87 minutes | B1ft | Follow through from their T value; condone lack of units |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Demonstration of relevant subtractions, or general explanation | B2ft, 1ft, 0 | 1B1ft: Partially complete/muddled account; 2B1ft: Complete, clear account |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: EFHT | B1 | CAO |
# Question 6:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Smaller number replacing larger number at C, D, G, H or T | M1 | Method mark for Dijkstra's algorithm |
| All values in boxes S, A, B, E and F correct | A1 | CAO |
| All values in boxes C and D correct | A1ft | Penalise order of labelling errors just once |
| All values in boxes G, H and T correct | A1 | CAO |
| Route: SBEFHT | B1 | CAO (not ft) |
| Time: 87 minutes | B1ft | Follow through from their T value; condone lack of units |
**Total: 6 marks**
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Demonstration of relevant subtractions, or general explanation | B2ft, 1ft, 0 | 1B1ft: Partially complete/muddled account; 2B1ft: Complete, clear account |
**Total: 2 marks**
## Part (c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: EFHT | B1 | CAO |
**Total: 1 mark**
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-07_602_1182_244_440}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
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.
\item Write down the quickest route from E to T .
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q6 [9]}}