| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2023 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.5 This is a straightforward application of two standard algorithms (Dijkstra's and Kruskal's) with no novel problem-solving required. While it's Further Maths content, both parts are routine textbook exercises requiring only careful execution of learned procedures on a small network, making it easier than average overall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (a) | A 1 0 |
| Answer | Marks |
|---|---|
| Shortest path: A – B – C – D | M1 |
| Answer | Marks |
|---|---|
| [3] | 3.1a |
| Answer | Marks |
|---|---|
| 1.1 | Using Dijkstra, a valid updating seen |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | (b) | BE = 2 ✓ |
| Answer | Marks |
|---|---|
| BE, CD, AE, BC | M1 |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Using Kruskal, list of (at least the first 5) arcs (and weights) in |
| Answer | Marks |
|---|---|
| 2 | 3 |
| 2 | 2 |
Question 2:
2 | (a) | A 1 0
B 3 4 E 2 3
4 3
C 4 9 D 5 11
11 9 15 12 11
Shortest path: A – B – C – D | M1
A1
B1
[3] | 3.1a
1.1
1.1 | Using Dijkstra, a valid updating seen
Permanent values all correct
Or from D:
A 5 11 B 3 7 C 2 2 D 1 0 E 4 9
15 11 7 2 9
A – B – C – D (not in reverse)
2 | (b) | BE = 2 ✓
CD = 2 ✓
AE = 3 ✓
AB = 4
BC = 5 ✓
CE = 8
DE = 9
AD = 15
Minimum spanning tree:
BE, CD, AE, BC | M1
A1
B1
[3] | 1.1
1.1
1.1 | Using Kruskal, list of (at least the first 5) arcs (and weights) in
increasing order of weight, o.e.
Allow BE, CD, AE, BC listed in order, with no others
BE and CD may be interchanged
Not choosing arc AB in list
AB indicated in a different way from BE etc
Allow AB completely missing from list
Choosing arcs BE, CD, AE, BC (only), allow A-E-B-C-D
From a correct tree seen or arcs listed (separately from Kruskal
working) (need not show arc weights)
For reference:
2 | 3
2 | 2
22 A network is shown below.\\
\includegraphics[max width=\textwidth, alt={}, center]{c9fb5dad-1069-46cd-b167-80b77016f03c-2_533_869_1160_244}
\begin{enumerate}[label=(\alph*)]
\item Use an appropriate algorithm to find the least weight (shortest) path from A to D.
\item Use Kruskal's algorithm to find a minimum spanning tree for the network.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2023 Q2 [6]}}