| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with MST |
| Difficulty | Moderate -0.3 This is a straightforward application of two standard D1 algorithms (Dijkstra and Kruskal) with no novel problem-solving required. Both parts are routine textbook exercises testing algorithmic execution rather than insight. The Kruskal part is even partially completed. Slightly easier than average A-level maths due to being purely procedural, though the dual-algorithm format adds minor complexity. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied | M1 | |
| Correct order of labelling | A1 | |
| Correct labels | A1 | |
| Correct working values | A1 | |
| Route ABCDFG, weight 12 | B1 | Route and weight both required |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum spanning tree drawn: AB=5, BC=2, CD=2, DE=1, DF=2, FG=1 | M1 | |
| Correct tree | A1 | |
| Total weight = 13 | B1 |
# Question 2:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied | M1 | |
| Correct order of labelling | A1 | |
| Correct labels | A1 | |
| Correct working values | A1 | |
| Route ABCDFG, weight 12 | B1 | Route and weight both required |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum spanning tree drawn: AB=5, BC=2, CD=2, DE=1, DF=2, FG=1 | M1 | |
| Correct tree | A1 | |
| Total weight = 13 | B1 | |
---2 Answer this question on the insert provided.
(i) Use Dijkstra's algorithm to find the least weight route from $A$ to $G$ in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_458_584_525_760}
\captionsetup{labelformat=empty}
\caption{Fig. 2.1}
\end{center}
\end{figure}
(ii) Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_421_533_1307_779}
\captionsetup{labelformat=empty}
\caption{Fig. 2.2}
\end{center}
\end{figure}
Complete the algorithm and give the total weight of your minimum spanning tree.
\hfill \mbox{\textit{OCR MEI D1 2005 Q2 [8]}}