| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| 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 with a small network, requiring only mechanical execution of a standard procedure plus brief explanations of basic algorithmic properties. The conceptual understanding needed for parts (ii) and (iii) is minimal—these are direct consequences of how Dijkstra's works that students learn by rote. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied | M1 | Dijkstra |
| Correct working values shown | A1 | working values |
| Correct order of labelling | B1 | order of labelling |
| Correct labels | B1 | labels |
| Shortest distance \(= 27\) | B1 | |
| Shortest route: ABCEF | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Because F was the final vertex labelled | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Because if there were to be a shorter route than BCEF from B to F, then A to B followed by it would give a shorter route from A to F; or "B is en route" | B1 |
# Question 3:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied | M1 | Dijkstra |
| Correct working values shown | A1 | working values |
| Correct order of labelling | B1 | order of labelling |
| Correct labels | B1 | labels |
| Shortest distance $= 27$ | B1 | |
| Shortest route: ABCEF | B1 | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Because F was the final vertex labelled | B1 | cao |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Because if there were to be a shorter route than BCEF from B to F, then A to B followed by it would give a shorter route from A to F; or "B is en route" | B1 | |
---3 The network shows distances between vertices where direct connections exist.\\
\includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-3_518_691_1742_687}\\
(i) Use Dijkstra's algorithm to find the shortest distance and route from A to F .\\
(ii) Explain why your solution to part (i) also provides the shortest distances and routes from A to each of the other vertices.\\[0pt]
(iii) Explain why your solution to part (i) also provides the shortest distance and route from B to F. [1]
\hfill \mbox{\textit{OCR MEI D1 2011 Q3 [8]}}