| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | June |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Standard +0.3 This is a standard D1 question combining routine algorithmic procedures (Dijkstra, Chinese Postman, nearest neighbour, Prim's). Each part requires straightforward application of well-practiced algorithms with no novel problem-solving. The multi-part structure and need to recognize the Chinese Postman problem adds slight complexity, but all techniques are core D1 syllabus material executed mechanically. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes7.04f Network problems: choosing appropriate algorithm |
| \(B\) | \(C\) | \(D\) | \(F\) | \(G\) | |
| \(B\) | - | 0.2 | 0.1 | 0.3 | 0.75 |
| \(C\) | 0.2 | - | 0.3 | 0.5 | 0.95 |
| \(D\) | 0.1 | 0.3 | - | 0.2 | 0.65 |
| \(F\) | 0.3 | 0.5 | 0.2 | - | 0.45 |
| \(G\) | 0.75 | 0.95 | 0.65 | 0.45 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Dijkstra's algorithm applied with temporary/permanent labels shown in order | M1 | |
| Correct permanent labels assigned in correct order | A1 A1 | |
| Shortest path identified correctly | A1 | |
| Route written down: e.g. \(A\)–\(B\)–\(D\)–\(F\)–\(G\) or similar with correct distance | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Chinese Postman (Route Inspection) problem | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Odd vertices identified (all vertices with odd degree) | M1 | |
| \(AB\) and \(EF\) must be repeated; shortest path pairings found | M1 | |
| Total = \(3.7 + 0.5 + 0.3 = 4.5\) km | A1 A1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Starting \(B\): nearest is \(D\) (0.1), then \(F\) (0.2), then \(C\) (0.5), then \(G\) (0.45) | M1 | |
| Total upper bound = \(0.1+0.2+0.3+0.45+0.75 = 1.8\) (returning to \(B\)) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Prim's on reduced table (no \(G\)): \(B\)→\(D\) (0.1)→\(F\) (0.2)→\(C\) (0.3 via...) | M1 | Order of vertices stated |
| Tree drawn correctly | A1 | |
| Total weight calculated | A1 | |
| Lower bound = tree weight + two smallest connections from \(G\) back... | A1 |
# Question 4:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Dijkstra's algorithm applied with temporary/permanent labels shown in order | M1 | |
| Correct permanent labels assigned in correct order | A1 A1 | |
| Shortest path identified correctly | A1 | |
| Route written down: e.g. $A$–$B$–$D$–$F$–$G$ or similar with correct distance | A1 | |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Chinese Postman (Route Inspection) problem | B1 | |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Odd vertices identified (all vertices with odd degree) | M1 | |
| $AB$ and $EF$ must be repeated; shortest path pairings found | M1 | |
| Total = $3.7 + 0.5 + 0.3 = 4.5$ km | A1 A1 A1 | |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| Starting $B$: nearest is $D$ (0.1), then $F$ (0.2), then $C$ (0.5), then $G$ (0.45) | M1 | |
| Total upper bound = $0.1+0.2+0.3+0.45+0.75 = 1.8$ (returning to $B$) | A1 | |
## Part (v)
| Answer | Mark | Guidance |
|--------|------|----------|
| Prim's on reduced table (no $G$): $B$→$D$ (0.1)→$F$ (0.2)→$C$ (0.3 via...) | M1 | Order of vertices stated |
| Tree drawn correctly | A1 | |
| Total weight calculated | A1 | |
| Lower bound = tree weight + two smallest connections from $G$ back... | A1 | |
---4 The network below represents a small village. The arcs represent the streets and the weights on the arcs represent distances in km .\\
\includegraphics[max width=\textwidth, alt={}, center]{7ca6d572-d776-4ad7-a0ed-9ec43c975585-04_503_1179_324_482}\\
(i) Use Dijkstra's algorithm to find the shortest path from $A$ to $G$. You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from $A$ to $G$.
Hannah wants to deliver newsletters along every street; she will start and end at $A$.\\
(ii) Which standard network problem does Hannah need to solve to find the shortest route that uses every arc?
The total weight of all the arcs is 3.7 km .\\
(iii) Hannah knows that she will need to travel $A B$ and $E F$ twice, once in each direction. With this information, use an appropriate algorithm to find the length of the shortest route that Hannah can use. Show all your working. (You may find the lengths of shortest paths between vertices by inspection.)
There are street name signs at each vertex except for $A$ and $E$. Hannah's friend Peter wants to check that the signs have not been vandalised. He will start and end at $B$.
The table below shows the complete set of shortest distances between vertices $B , C , D , F$ and $G$.
\begin{center}
\begin{tabular}{ c | c | c | c | c | c }
& $B$ & $C$ & $D$ & $F$ & $G$ \\
\hline
$B$ & - & 0.2 & 0.1 & 0.3 & 0.75 \\
\hline
$C$ & 0.2 & - & 0.3 & 0.5 & 0.95 \\
\hline
$D$ & 0.1 & 0.3 & - & 0.2 & 0.65 \\
\hline
$F$ & 0.3 & 0.5 & 0.2 & - & 0.45 \\
\hline
$G$ & 0.75 & 0.95 & 0.65 & 0.45 & - \\
\hline
\end{tabular}
\end{center}
(iv) Apply the nearest neighbour method to this table, starting from $B$, to find an upper bound for the distance that Peter must travel.\\
(v) Apply Prim's algorithm to the matrix formed by deleting the row and column for vertex $G$ from the table. Start building your tree at vertex $B$.
Draw your tree. Give the order in which vertices are built into your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Peter must travel.
\hfill \mbox{\textit{OCR D1 2010 Q4 [17]}}