| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Practical modelling questions |
| Difficulty | Moderate -0.5 Part (i) is a standard application of Dijkstra's algorithm on a small network, requiring only mechanical execution of a well-practiced procedure. Part (ii) asks for basic critical thinking about the model's limitations, which is routine for D1 modelling questions. The question is slightly easier than average due to its straightforward setup and limited problem-solving demands. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Dijkstra's algorithm applied | M1 | Dijkstra |
| Correct order of labelling | A1 | order |
| Correct final labels | A1 | labels |
| Correct working values shown | A1 | working values |
| Cheapest cost = £11 | B1 | £11 |
| Route: \([\text{start (£2 starter)}] \to A \text{ (£3 main)} \to E \text{ (£3 main)} \to B \text{ (£1 main)} \to F \text{ (£2 sweet)} \to [\text{end}]\) | B1 | route |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Repeated mains | B1 | |
| Directed network | B1 |
# Question 3:
## Part (i)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Dijkstra's algorithm applied | M1 | Dijkstra |
| Correct order of labelling | A1 | order |
| Correct final labels | A1 | labels |
| Correct working values shown | A1 | working values |
| Cheapest cost = £11 | B1 | £11 |
| Route: $[\text{start (£2 starter)}] \to A \text{ (£3 main)} \to E \text{ (£3 main)} \to B \text{ (£1 main)} \to F \text{ (£2 sweet)} \to [\text{end}]$ | B1 | route |
## Part (ii)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Repeated mains | B1 | |
| Directed network | B1 | |
---3 Whilst waiting for her meal to be served, Alice tries to construct a network to represent the meals offered in the restaurant.\\
\includegraphics[max width=\textwidth, alt={}, center]{9bb2d545-3764-4930-a8a8-9dc5e25d0836-3_684_1310_365_379}\\
(i) Use Dijkstra's algorithm to find the cheapest route through the undirected network from "start" to "end". Give the cost and describe the route. Use the lettering given on the network in your answer book.\\
(ii) Criticise the model and suggest how it might be improved.
\hfill \mbox{\textit{OCR MEI D1 2009 Q3 [8]}}