| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.5 This is a standard application of Dijkstra's algorithm, a core D1 topic. While it requires careful bookkeeping across 10 vertices and systematic labeling, it's a routine algorithmic procedure with no problem-solving insight needed. The 10 marks reflect length rather than conceptual difficulty. Slightly easier than average since it's pure algorithm execution without any novel elements. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| so Li Ma Le Y H is shortest route, length = 135 miles | M3 A3 | M1 A1 A2 |
[Network diagram with nodes P, Li, C, Ma, Le, S, Y, Mi, D, H and labeled edges showing weights and distances]
label H – label Y = 37 = weight YH
label Y – label Le = 23 = weight LeY
label Le – label Ma = 40 = weight MaLe
label Ma – label Li = 35 = weight LiMa
so Li Ma Le Y H is shortest route, length = 135 miles | M3 A3 | M1 A1 A2 | (10) |
---\textit{This question should be answered on the sheet provided.}
\includegraphics{figure_1}
Figure 1 above shows distances in miles between 10 cities.
Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:
\begin{enumerate}[label=(\roman*)]
\item the order in which you labelled the vertices,
\item how you used your labelled diagram to find the shortest route. [10 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q4 [10]}}