| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| 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 procedural execution of a standard algorithm. Part (ii) is trivial counting (n applications for n vertices). No problem-solving insight needed, just careful bookkeeping—easier than average A-level questions which typically require some conceptual understanding or multi-step reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
1 (i) Use Dijkstra's algorithm to find the shortest distances and corresponding routes from A to each of the other vertices in the given network.\\
\includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-2_588_792_632_632}\\
(ii) If the shortest distances and routes between every pair of vertices are required how many applications of Dijkstra will be needed?
\hfill \mbox{\textit{OCR MEI D1 2010 Q1 [8]}}