| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 25 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Moderate -0.3 This is a standard D1 question testing routine application of Dijkstra's algorithm and the Chinese Postman Problem. While multi-part with 16 marks total, each part follows textbook procedures: (i) mechanical application of Dijkstra, (ii) recall of problem name, (iii) standard CPP algorithm, (iv) simple modification, (v-vi) basic nearest neighbour method. No novel insight required, just careful execution of learned algorithms. Slightly easier than average A-level due to being purely algorithmic with no proof or problem-solving creativity needed. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Length = 9.5 miles | B1 | Both 6 and 5 shown at \(D\) (5 must appear as perm label only) [14, 13.5 and 10.5 shown at \(G\)] |
| M1 | No extra temporary labels. All temporary labels correct [condone perm values only appearing as perm labels] | |
| A1 | [Dep on both M marks] | |
| [7] |
| Answer | Marks | Guidance |
|---|---|---|
| Route Inspection problem | B1 | cao |
| [1] |
| Answer | Marks |
|---|---|
| B1 | Identifying or using \(A, D, E, H\) |
| M1 | Attempting at least one pairing |
| A1 | At least one correct pairing or correct total |
| Answer | Marks | Guidance |
|---|---|---|
| Length = \(67.5 + 10 = 77.5\) miles | M1 | Adding their 10 to 67.5 |
| A1 | 77.5 (cao) | |
| [5] |
| Answer | Marks | Guidance |
|---|---|---|
| 3.5 + 67.5 = 71 miles | B1 | cao [NOT \(DE\) or \(D - F - E\)] |
| B1 | cao | |
| [2] |
| Answer | Marks | Guidance |
|---|---|---|
| \(E\) and \(H\) are missed out | B1 | Showing route as far as \(D\) and then explaining the problem |
| [1] |
| Answer | Marks | Guidance |
|---|---|---|
| 37.5 miles | M1 | [If final C is missing \(\Rightarrow\) M1, A0] |
| A1 | [A diagram needs arrows for A1] | |
| B1 | 37.5 (cao) | |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| Lower bound = 24 miles | M1 | A spanning tree on reduced network (may show \(AB, AD\)) |
| A1 | Correct minimum spanning tree marked, with no extra arcs | |
| B1 | cao | |
| B1 | cao | |
| M1 | \(8 +\) their 16 (or implied) | |
| A1 | cao | |
| [6] |
## (i)
Route = $A - B - D - F - H$
Length = 9.5 miles | B1 | Both 6 and 5 shown at $D$ (5 must appear as perm label only) [14, 13.5 and 10.5 shown at $G$]
| M1 | No extra temporary labels. All temporary labels correct [condone perm values only appearing as perm labels]
| A1 | [Dep on both M marks]
| [7] |
## (ii)
Route Inspection problem | B1 | cao
| [1] |
## (iii)
Odd nodes: $A, D, E$ and $H$
$AD = 5 \quad AE = 8 \quad AH = 9.5$
$EH = 5 \quad DH = 4.5 \quad DE = 3.5$
| B1 | Identifying or using $A, D, E, H$
| M1 | Attempting at least one pairing
| A1 | At least one correct pairing or correct total
Repeat $AD$ ($A - B - D$) and $EH$ ($E - F - H$)
Length = $67.5 + 10 = 77.5$ miles | M1 | Adding their 10 to 67.5
| A1 | 77.5 (cao)
| [5] |
## (iv)
Repeat arcs $EF$ and $FD$
3.5 + 67.5 = 71 miles | B1 | cao [NOT $DE$ or $D - F - E$]
| B1 | cao
| [2] |
## (v)
$A - B - C - G - F - D$
then method stalls
$E$ and $H$ are missed out | B1 | Showing route as far as $D$ and then explaining the problem
| [1] |
## (vi)
$C - B - A - D - F - E - H - G - C$
37.5 miles | M1 | [If final C is missing $\Rightarrow$ M1, A0]
| A1 | [A diagram needs arrows for A1]
| B1 | 37.5 (cao)
| [3] |
## (vii)
Nodes: $B C D F E H G$
Weight = 16 miles
[Two shortest arcs from $A$ are $AB$ and $AD$]
$2 + 6 + 16$
Lower bound = 24 miles | M1 | A spanning tree on reduced network (may show $AB, AD$)
| A1 | Correct minimum spanning tree marked, with no extra arcs
| B1 | cao
| B1 | cao
| M1 | $8 +$ their 16 (or implied)
| A1 | cao
| [6] |
---Answer this question on the insert provided.
The vertices in the network below represent the junctions between main roads near Ayton (A). The arcs represent the roads and the weights on the arcs represent distances in miles.
\includegraphics{figure_4}
\begin{enumerate}[label=(\roman*)]
\item On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from A to H. 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 H and give its length in miles. [7]
\end{enumerate}
Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{1}
\item Which standard network problem does Simon need to solve to find the shortest route that uses every arc? [1]
\end{enumerate}
The total weight of all the arcs is 67.5 miles.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{2}
\item Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) [5]
\end{enumerate}
Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from A and ending at H.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{3}
\item Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? [2]
\end{enumerate}
There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{4}
\item Show that the nearest neighbour method fails on this network if it is started from A. [1]
\item Apply the nearest neighbour method starting from C to find an upper bound for the distance that Amber must travel. [3]
\item Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node A and all the arcs that are directly joined to node A. \textbf{Start building your tree at node B.} (You do \textit{not} need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert.
Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel. [6]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2009 Q4 [25]}}