| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with vertex or edge exclusion |
| Difficulty | Moderate -0.3 This is a straightforward application of Dijkstra's algorithm with a standard follow-up requiring re-application with one vertex excluded. Part (a) is routine algorithmic execution, part (b) tests basic understanding of reading back the route, and part (c) simply requires repeating the algorithm while avoiding vertex D—no novel problem-solving or insight required, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Dijkstra's algorithm applied correctly; S=0, C=8, F=14, B=23(24), A=16, D=33, E=45, T=65 | M1, A1(SCFA) | Big replaced by smaller at least once at B, D, E or T |
| B and D boxes ft correctly | A1ft(BD) | Penalise order of labelling only once per question |
| E and T correct | A1(ET) | Penalise order of labelling only once |
| Route: SCFBDET; length 65 | 1B1; 2B1ft (6) | Route CAO; final value ft |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Working back: \(65-20=45\) ET; \(45-12=33\) DE; \(33-10=23\) BD; \(23-9=14\) FB; \(14-6=8\) CF; \(8-8=0\) SC | B2ft, 1ft, 0 (2) | Attempting explanation with at least 3 stages or one half of general explanation for 1B1; correct explanation all stages both halves for 2B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Route: SCFBET; length 68 | B1; B1 (2) | Route CAO; length CAO |
## Question 5:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied correctly; S=0, C=8, F=14, B=23(24), A=16, D=33, E=45, T=65 | M1, A1(SCFA) | Big replaced by smaller at least once at B, D, E or T |
| B and D boxes ft correctly | A1ft(BD) | Penalise order of labelling only once per question |
| E and T correct | A1(ET) | Penalise order of labelling only once |
| Route: SCFBDET; length 65 | 1B1; 2B1ft **(6)** | Route CAO; final value ft |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Working back: $65-20=45$ ET; $45-12=33$ DE; $33-10=23$ BD; $23-9=14$ FB; $14-6=8$ CF; $8-8=0$ SC | B2ft, 1ft, 0 **(2)** | Attempting explanation with at least 3 stages or one half of general explanation for 1B1; correct explanation all stages both halves for 2B1 |
### Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Route: SCFBET; length 68 | B1; B1 **(2)** | Route CAO; length CAO |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4ad45e8f-f50a-4125-866b-a6951f85600f-6_785_1463_191_301}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from S to T . State your shortest route and its length.\\
(6)
\item Explain how you determined your shortest route from your labelled diagram.\\
(2)
Due to flooding, the roads in and out of D are closed.
\item Find the shortest route from S to T avoiding D . State your shortest route and its length.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q5 [10]}}