| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Session | Specimen |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Standard +0.3 This is a standard D1 question combining routine Dijkstra's algorithm with Chinese Postman and nearest neighbour algorithms. Part (i) is textbook Dijkstra application, part (ii) requires identifying odd vertices and pairing them (standard Chinese Postman), and part (iii) is straightforward nearest neighbour. All three parts follow algorithmic procedures taught directly in the specification with no novel problem-solving required, making this slightly easier than average overall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct temporary labels at each vertex | M1 | Evidence of Dijkstra working |
| Correct order of becoming permanent shown | A1 | |
| All permanent values correct | A1 | |
| Least travel time = \(54\) minutes | A1 | cao |
| Route: \(A - B - C - D\) | A1 | ft from their working |
# Question 6:
## Part (i) - Dijkstra's Algorithm
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct temporary labels at each vertex | M1 | Evidence of Dijkstra working |
| Correct order of becoming permanent shown | A1 | |
| All permanent values correct | A1 | |
| Least travel time = $54$ minutes | A1 | cao |
| Route: $A - B - C - D$ | A1 | ft from their working |6 [Answer part (i) of this question on the insert provided.]\\
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes.\\
\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}\\
(i) Use Dijkstra's algorithm, starting from checkpoint $\boldsymbol { A }$, to find the least travel time from $A$ to $D$. You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from $A$ to $D$.\\
(ii) By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at $A$. You should show your method clearly.\\
(iii) Starting from $A$, apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from $A$ and finishing at $D$.
\hfill \mbox{\textit{OCR D1 Q6 [15]}}