| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2005 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm with route extraction |
| Difficulty | Standard +0.8 This question requires reverse-engineering a network from completed Floyd's algorithm matrices, demanding solid understanding of how the algorithm works and the relationship between distance and route matrices. While methodical, it involves multiple steps of logical deduction and is more challenging than standard 'apply Floyd's algorithm' questions, placing it moderately above average difficulty. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | |
| \(\mathbf { 1 }\) | 4 | 2 | 3 | 9 |
| \(\mathbf { 2 }\) | 2 | 2 | \(\mathbf { 1 }\) | 7 |
| \(\mathbf { 3 }\) | 3 | \(\mathbf { 1 }\) | 2 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct graph with vertices 1–4 and edges with weights (2,3,6,7,9,1,12) | M1 A1 | loops optional |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First vertex en route is 3; first vertex en route from 3 to 1 is 2; first vertex en route from 2 to 1 is 1 | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct graph with 5 vertices, edges with weights (2,3,5,1,6,1) | B1 | |
| Correct updated graph with loops and all edges (5,2,2,3,4,3,1,6,4,5,2,1,2) | M1 A1 | loops optional |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Distance matrix correct | B1 | distance matrix |
| Route matrix constructed using Prim | M1 | route matrix |
| Route matrix correct | A1 cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: \(1\ 2\ 3\ 5\ 4\ 1\) | M1 | |
| Distance: 14 | A1 | |
| Full route: \(1\ 2\ 3\ 2\ 5\ 4\ 5\ 2\ 1\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Prim applied on matrix correctly | M1 A1 | Prim on matrix |
| Lower bound is \(5 + 2 + 3 = 10\) | B1 B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. route \(1\ 2\ 5\ 4\ \underline{3\ 2\ 3}\ 1\) | M1 A1 cao | |
| Total distance: 19 | B1 |
# Question 3:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct graph with vertices 1–4 and edges with weights (2,3,6,7,9,1,12) | M1 A1 | loops optional |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First vertex en route is 3; first vertex en route from 3 to 1 is 2; first vertex en route from 2 to 1 is 1 | M1 A1 | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct graph with 5 vertices, edges with weights (2,3,5,1,6,1) | B1 | |
| Correct updated graph with loops and all edges (5,2,2,3,4,3,1,6,4,5,2,1,2) | M1 A1 | loops optional |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Distance matrix correct | B1 | distance matrix |
| Route matrix constructed using Prim | M1 | route matrix |
| Route matrix correct | A1 cao | |
## Part (v)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: $1\ 2\ 3\ 5\ 4\ 1$ | M1 | |
| Distance: 14 | A1 | |
| Full route: $1\ 2\ 3\ 2\ 5\ 4\ 5\ 2\ 1$ | A1 | |
## Part (vi)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Prim applied on matrix correctly | M1 A1 | Prim on matrix |
| Lower bound is $5 + 2 + 3 = 10$ | B1 B1 | |
## Part (vii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. route $1\ 2\ 5\ 4\ \underline{3\ 2\ 3}\ 1$ | M1 A1 cao | |
| Total distance: 19 | B1 | |3 The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2.
Distance Matrix
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\multicolumn{1}{l}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ \\
\hline
$\mathbf { 1 }$ & 4 & 2 & 3 & 9 \\
\hline
$\mathbf { 2 }$ & 2 & 2 & $\mathbf { 1 }$ & 7 \\
\hline
$\mathbf { 3 }$ & 3 & $\mathbf { 1 }$ & 2 & 6 \\
\hline
\end{tabular}
\end{center}
\hfill \mbox{\textit{OCR MEI D2 2005 Q3 [20]}}