| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2019 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.3 This is a standard Further Maths Decision question covering routine Dijkstra's algorithm application and basic graph theory (Chinese Postman problem). While it requires multiple techniques and careful execution across several parts, each component is a textbook application with no novel insight required. The matrix format and multi-part structure add length but not conceptual difficulty. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| A | B | C | D | E | F | G | H | |
| A | - | 130 | 100 | - | - | 250 | - | - |
| B | 130 | - | - | 50 | - | - | 170 | 100 |
| C | 100 | - | - | - | 80 | 170 | - | 90 |
| D | - | 50 | - | - | - | - | 120 | - |
| E | - | - | 80 | - | - | 140 | - | 120 |
| F | 250 | - | 170 | - | 140 | - | - | - |
| G | - | 170 | - | 120 | - | - | - | 90 |
| H | - | 100 | 90 | - | 120 | - | 90 | - |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (a) | Matrix is symmetric about lead diagonal |
| Matrix is its own transpose | Rows are same as columns |
| Answer | Marks | Guidance |
|---|---|---|
| (b) | A – C - E | B1 |
| (c) | Vertex Temporary Order of Permanent |
| Answer | Marks |
|---|---|
| H 90 2 90 | M1 |
| Answer | Marks |
|---|---|
| B1ft | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | Working may be done on a network. |
| Answer | Marks |
|---|---|
| permanent labels | Dependent on both M marks |
| Answer | Marks | Guidance |
|---|---|---|
| (d) | 2 × length of all roads = 3220 metres | B1 |
| (e) | (i) | AE = 180 AF = 250 AG = 280 |
| Answer | Marks |
|---|---|
| = 2030 metres | M1 |
| Answer | Marks |
|---|---|
| A1 | 3.3 |
| Answer | Marks |
|---|---|
| 3.5a | Considering these three pairs |
| Answer | Marks |
|---|---|
| 2030m or 2.03 km, with units | AC, CE = 180 |
| Answer | Marks |
|---|---|
| (ii) | Length = 1750 m |
| Start at A | B1 |
| B1 | 3.4 |
| 3.1b | 1750 or 1.75 as shortest length |
| Or start at G | A or G (or both) as start |
| Answer | Marks |
|---|---|
| Vertex | Temporary |
| labels | Order of |
| Answer | Marks |
|---|---|
| labelling | Permanent |
| Answer | Marks | Guidance |
|---|---|---|
| A | 300, 280 | 7 |
| B | 170 | 4 |
| C | 180 | 5 |
| D | 120 | 3 |
| E | 210 | 6 |
| F | 350 | 8 |
| G | 1 | 0 |
| H | 90 | 2 |
Question 5:
5 | (a) | Matrix is symmetric about lead diagonal | E1 | 2.5 | Table is symmetric about diagonal
Matrix is its own transpose | Rows are same as columns
Examples and ‘always true’
(b) | A – C - E | B1 | 3.1a | ACE or AC, CE in any form
(c) | Vertex Temporary Order of Permanent
labels permanent label
labelling
A 300, 280 7 280
B 170 4 170
C 180 5 180
D 120 3 120
E 210 6 210
F 350 8 350
G 1 0
H 90 2 90 | M1
M1
A1
B1ft | 1.1
1.1
1.1
1.1 | Working may be done on a network.
Temp labels 170 at B, 120 at D and
90 at H
Updating at A
All permanent labels correct and no
extra temp labels
Order of labelling correct for their
permanent labels | Dependent on both M marks
From 1 to 8
(d) | 2 × length of all roads = 3220 metres | B1 | 3.2a | 3220m or 3.22 km, with units
(e) | (i) | AE = 180 AF = 250 AG = 280
FG = 350 EG = 210 EF = 140
530 460 420
Repeat ACHG and EF
420 + 1610
= 2030 metres | M1
B1
A1
M1
A1 | 3.3
1.1
3.4
3.4
3.5a | Considering these three pairs
AE = 180 seen
530, 460 and 420 seen
Their 420 + [1610 or from their (ii)]
2030m or 2.03 km, with units | AC, CE = 180
Addition seen (or implied
form correct answer)
SC if a candidate gives 1880 and
explains that they have doubled the
shortest route from B to an odd
vertex (BA = 130) and EF (= 140)
(ii) | Length = 1750 m
Start at A | B1
B1 | 3.4
3.1b | 1750 or 1.75 as shortest length
Or start at G | A or G (or both) as start
[14]
Vertex | Temporary
labels | Order of
permanent
labelling | Permanent
label
A | 300, 280 | 7 | 280
B | 170 | 4 | 170
C | 180 | 5 | 180
D | 120 | 3 | 120
E | 210 | 6 | 210
F | 350 | 8 | 350
G | 1 | 0
H | 90 | 2 | 905 A network is represented by the distance matrix below. For this network a direct connection between two vertices is always shorter than an indirect connection.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G & H \\
\hline
A & - & 130 & 100 & - & - & 250 & - & - \\
\hline
B & 130 & - & - & 50 & - & - & 170 & 100 \\
\hline
C & 100 & - & - & - & 80 & 170 & - & 90 \\
\hline
D & - & 50 & - & - & - & - & 120 & - \\
\hline
E & - & - & 80 & - & - & 140 & - & 120 \\
\hline
F & 250 & - & 170 & - & 140 & - & - & - \\
\hline
G & - & 170 & - & 120 & - & - & - & 90 \\
\hline
H & - & 100 & 90 & - & 120 & - & 90 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item How does the distance matrix show that the arcs are undirected?
The shortest distance from A to E is 180 .
\item Write down the shortest route from A to E .
\item Use Dijkstra's algorithm on the distance matrix to find the length of the shortest route from $\mathbf { G }$ to each of the other vertices.
The arcs represent roads and the weights represent distances in metres. The total length of all the roads is 1610 metres.
Emily and Stephen have set up a company selling ice-creams from a van.
\item Emily wants to deliver leaflets to the houses along each side of each road. Find the length of the shortest continuous route that Emily can use.
\item Stephen wants to drive along each road in the ice-cream van.
\begin{enumerate}[label=(\roman*)]
\item Determine the length of the shortest route for Stephen if he starts at B.
\item Stephen wants to use the shortest possible route.
\begin{itemize}
\end{enumerate}\item Find the length of the shortest possible route.
\item Write down the start and end vertices of this route.
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2019 Q5 [14]}}