| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Incomplete Dijkstra reconstruction |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm with clear instructions and a partial network. Students only need to apply the standard algorithm mechanically until they can't proceed further due to missing information. It requires recall of the algorithm but no problem-solving or adaptation, making it easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks |
|---|---|
| Temporary labels at \(B\) correct, no extras | M1 |
| Temporary labels at \(E\) correct, no extras | M1 |
| Permanent labels correct at \(B\), \(C\) and \(E\) (dependent on both M marks) | A1 |
| Order of labelling correct at \(B\), \(C\) and \(E\) | B1 |
| Temporary labels at \(D\) correct | M1 |
| No permanent label at \(D\) | A1 |
| \(\mathbf{6}\) |
**Temporary labels at $B$ correct, no extras** | M1 |
**Temporary labels at $E$ correct, no extras** | M1 |
**Permanent labels correct at $B$, $C$ and $E$ (dependent on both M marks)** | A1 |
**Order of labelling correct at $B$, $C$ and $E$** | B1 |
**Temporary labels at $D$ correct** | M1 |
**No permanent label at $D$** | A1 |
| | $\mathbf{6}$ |2 Answer this question on the insert provided.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{8f17020a-14bf-4459-9241-1807b954a629-2_659_1136_1720_530}
\end{center}
This diagram shows part of a network. There are other arcs connecting $D$ and $E$ to other parts of the network. Apply Dijkstra's algorithm starting from $A$, as far as you are able, showing your working. Note: you will not be able to give permanent labels to all the vertices shown.
\hfill \mbox{\textit{OCR D1 2006 Q2 [6]}}