| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.3 This is a straightforward application of Dijkstra's algorithm (a standard D1 procedure) followed by a simple extension requiring two applications to find a route via F. The algorithm is mechanical and well-practiced, requiring no novel insight—just careful execution and addition of two shortest paths. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| M1 | ||
| A1 (A,B,C,D) | ||
| Shortest path S to T: SADGEHT | A1 | |
| Length of shortest path S to T: 30 (miles) | A1ft (6) | |
| Shortest path S to T via F: SCBFEHT | B1 | |
| Length is 31 (miles) | B1 (2) | |
| 8 marks |
| | | M1 |
| | | A1 (A,B,C,D) |
| Shortest path S to T: SADGEHT | | A1 |
| Length of shortest path S to T: 30 (miles) | | A1ft (6) |
| | | |
| Shortest path S to T via F: SCBFEHT | | B1 |
| Length is 31 (miles) | | B1 (2) |
| | | 8 marks |
**Notes for Question 4:**
- a1M1: A larger value replaced by a smaller value at least once in the working values at either B or E or F or H or T.
- a1A1: All values in A, B, C and D correct. The working values at B must be in the correct order.
- a2A1: All values in E, F and G correct and the working values in the correct order. Penalise order of labelling only once per question (F, G and E labelled in that order and F must be labelled after A, B, C and D).
- a3A1ft: All values in H and T ft correct and the working values in the correct order. Penalise order of labelling only once per question (H and T labelled in that order and H labelled after all other nodes).
- a4A1: Route CAO.
- a5A1ft: ft on their final value (if answer is not 30 ft their final value at T).
- b1B1: Route CAO
- b2B1: Length CAO (condone lack of (or incorrect) units throughout).
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-5_780_1717_276_175}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Liz wishes to travel from S to T .
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from S to T . State your path and its length.
On a particular day, Liz must include F in her route.
\item Find the shortest path from S to T that includes F , and state its length.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q4 [8]}}