| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm, a standard D1 topic requiring methodical execution of a learned procedure rather than problem-solving. Part (b) requires only observation of the completed table. The 7 marks reflect the mechanical steps involved, not conceptual difficulty. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks |
|---|---|
| M1 (Dijkstra) | |
| A1 | |
| A1, (4) |
| Answer | Marks |
|---|---|
| Traceback. Include or xy if y is already on the path end weight on xy + final label of y - final label of x or a detailed account for the question. Path is (AEFGHL) of length 13 or (AEIJKL) | B2, I, O |
| A1 | |
| State other path | B1, (4) |
## (a)
| M1 (Dijkstra) |
| A1 |
| A1, (4) |
## (b)
Traceback. Include or xy if y is already on the path end weight on xy + final label of y - final label of x or a detailed account for the question. Path is (AEFGHL) of length 13 or (AEIJKL) | B2, I, O |
| A1 |
State other path | B1, (4) |
---\includegraphics{figure_1}
Figure 1 shows a network of roads. Erica wishes to travel from $A$ to $L$ as quickly as possible. The number on each edge gives the time, in minutes, to travel along that road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find a quickest route from $A$ to $L$. Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling. [7]
\item Show that there is another route which also takes the minimum time [1]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q4 [8]}}