| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with vertex or edge exclusion |
| Difficulty | Moderate -0.3 This is a straightforward application of Dijkstra's algorithm followed by a simple observation question. Part (i) is routine algorithmic execution, and part (ii) requires only identifying the second-shortest path from the working already done—no re-calculation needed. Slightly easier than average due to the mechanical nature and the gift of part (ii). |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Least weight route: AFBGED, Weight = 10 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 11 | B1 | From working value. Can't be bettered since new least weight must be bigger than 10. |
**Part (i)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Least weight route: AFBGED, Weight = 10 | B1 | |
**Part (ii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| 11 | B1 | From working value. Can't be bettered since new least weight must be bigger than 10. |1 Answer this question on the insert provided.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-2_658_739_466_662}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
(i) Apply Dijkstra's algorithm to the copy of Fig. 1 in the insert to find the least weight route from A to D.
Give your route and its weight.\\
(ii) Arc DE is now deleted. Write down the weight of the new least weight route from A to D , and explain how your working in part (i) shows that it is the least weight.\\[0pt]
[2]
\hfill \mbox{\textit{OCR MEI D1 2006 Q1 [8]}}