| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with MST |
| Difficulty | Moderate -0.3 This is a straightforward application of two standard D1 algorithms (Dijkstra and either Prim's or Kruskal's) with no conceptual complications. Both parts require only routine execution of learned procedures on a small network, making it slightly easier than average for A-level but still requiring careful systematic work. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied correctly with working values shown | M1 | Dijkstra (if working values correct at D) |
| Correct working values | A1 | working values |
| Correct order of labelling | B1 | order of labelling labels |
| Correct labels | B1 | labels |
| Route: ABDCF, Time: 51 minutes | B1 | route and time |
| [5] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Methodology indicated (Prim's/Kruskal's) | B1 | methodology indicated |
| Correct minimum spanning tree shown (edges: AB=10, BD=5, DF=18 (via 15), CE, EF=19) | B1 | correct min connector |
| Time: 52 minutes | B1 | cao |
| [3] |
# Question 1:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied correctly with working values shown | M1 | Dijkstra (if working values correct at D) |
| Correct working values | A1 | working values |
| Correct order of labelling | B1 | order of labelling labels |
| Correct labels | B1 | labels |
| Route: ABDCF, Time: 51 minutes | B1 | route and time |
| **[5]** | | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Methodology indicated (Prim's/Kruskal's) | B1 | methodology indicated |
| Correct minimum spanning tree shown (edges: AB=10, BD=5, DF=18 (via 15), CE, EF=19) | B1 | correct min connector |
| Time: 52 minutes | B1 | cao |
| **[3]** | | |
---1 The weights on the arcs in the network represent times in minutes to travel between vertices.\\
\includegraphics[max width=\textwidth, alt={}, center]{d1e0f047-6484-435b-a685-2cbbf81a6b02-2_606_782_402_628}\\
(i) Use Dijkstra's algorithm to find the fastest route from A to F . Give the route and the time.\\
(ii) Use an algorithm to find the minimum connector for the network, showing your working. Find the minimum time to travel from A to F using only arcs in the minimum connector.
\hfill \mbox{\textit{OCR MEI D1 2013 Q1 [8]}}