| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm application |
| Difficulty | Easy -1.2 This is a straightforward Decision Mathematics question requiring only basic understanding of Floyd's algorithm mechanics and a simple contextual explanation. Part (i) is trivial reasoning about real-world path constraints, and completing Floyd's algorithm iteration involves routine table updates following a memorized procedure with no problem-solving insight required. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| \cline { 2 - 7 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | \(\mathbf { 5 }\) | \(\mathbf { 6 }\) |
| \(\mathbf { 1 }\) | \(\infty\) | 15 | \(\infty\) | \(\infty\) | 7 | 8 |
| \(\mathbf { 2 }\) | 15 | 30 | 6 | 2 | 6 | 23 |
| Answer | Marks | Guidance |
|---|---|---|
| The route via vertex 4 may be a shorter/quicker path than the direct arc, e.g. \(2 \to 4 \to 3\) takes \(2+3=5 < 6\) | B1 | Accept any valid reason relating to the triangle inequality not holding |
| Answer | Marks | Guidance |
|---|---|---|
| Second iteration (pivot on vertex 2). Update any entry \(D[i][j]\) where \(D[i][2]+D[2][j] < D[i][j]\): Row 1: \(D[1][3]\): \(15+6=21 > \infty\)? No, \(\infty \to 21\); \(D[1][4]\): \(15+2=17 > \infty \to 17\); \(D[1][6]\): \(15+23=38 > 23\)? No change. Etc. Full updated distance and route matrices. | M1 A1 A1 A1 | M1 for correct method; A1 for each correct updated row (3 rows correctly updated) |
# Question 2:
## Part (i)
| The route via vertex 4 may be a shorter/quicker path than the direct arc, e.g. $2 \to 4 \to 3$ takes $2+3=5 < 6$ | B1 | Accept any valid reason relating to the triangle inequality not holding |
## Part (ii)
| Second iteration (pivot on vertex 2). Update any entry $D[i][j]$ where $D[i][2]+D[2][j] < D[i][j]$: Row 1: $D[1][3]$: $15+6=21 > \infty$? No, $\infty \to 21$; $D[1][4]$: $15+2=17 > \infty \to 17$; $D[1][6]$: $15+23=38 > 23$? No change. Etc. Full updated distance and route matrices. | M1 A1 A1 A1 | M1 for correct method; A1 for each correct updated row (3 rows correctly updated) |
---2 The network is a representation of a show garden. The weights on the arcs give the times in minutes to walk between the six features represented by the vertices, where paths exist.\\
\includegraphics[max width=\textwidth, alt={}, center]{c3a528e4-b5fe-4bff-a77e-e3199bb225a1-3_483_985_342_539}\\
(i) Why might it be that the time taken to walk from vertex $\mathbf { 2 }$ to vertex $\mathbf { 3 }$ via vertex $\mathbf { 4 }$ is less than the time taken by the direct route, i.e. the route from $\mathbf { 2 }$ to $\mathbf { 3 }$ which does not pass through any other vertices?
The matrices shown below are the results of the first iteration of Floyd's algorithm when applied to the network.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\cline { 2 - 7 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ & $\mathbf { 5 }$ & $\mathbf { 6 }$ \\
\hline
$\mathbf { 1 }$ & $\infty$ & 15 & $\infty$ & $\infty$ & 7 & 8 \\
\hline
$\mathbf { 2 }$ & 15 & 30 & 6 & 2 & 6 & 23 \\
\hline
\end{tabular}
\end{center}
\hfill \mbox{\textit{OCR MEI D2 2010 Q2 [16]}}