| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm with a standard network diagram, requiring only mechanical execution of the algorithm and basic interpretation. Part (a)(i) is routine bookwork, parts (ii)-(iii) require minimal reasoning about path composition, and part (b) is a standard Chinese Postman problem setup. The question tests procedural fluency rather than problem-solving insight, making it easier than average for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct temporary labels at \(D\) and \(E\) | M1 | For correct temporary labels at \(D\) and \(E\) (condone extras here) |
| All temporary labels correct with no extras | A1 | Answer should be on insert |
| Value 38 at \(J\) | M1 | |
| All permanent labels correct | A1 | |
| Correct order of assigning permanent labels: \(A, B, C, D, G, E, F, H, J\) | B1 | |
| Shortest route: \(A-B-G-E\), Length \(= 900\) | B1 | For correct route and length; accept route reversed and accept length \(= 9\) |
| Shortest route: \(A-C-D-F-H-J\), Length \(= 3800\) | B1 | For correct route and length; accept route reversed and accept length \(= 38\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Length: 4700 metres | B1 | For 47 or 4700; follow through from (i) if possible |
| \(E-G-B-A-C-D-F-H-J\) | M1 | For \(E-G-B-A\), or reversed, as part of a longer route |
| M1 | For \(A-C-D-F-H-J\), or reversed, as part of a longer route | |
| A1 | For whole route correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(G-B-A-C-D-F-H\); \(E\) and \(J\) will be left out (either is sufficient) | M1 | For identifying that route will not visit every vertex |
| A1 | May be implied |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Odd nodes are \(A, C, D, E, F, G\) | ||
| Need to pair \(C, D, F, G\) in the shortest way | M1 | For trying to pair \(C, D, F, G\) (and no others) |
| \(CD = 3\) and \(FG = 7 \Rightarrow 10\); \((CF=10,\ DG=11\) and \(CG=8,\ DF=7)\) | A1 | For \(CD\), \(FG\) or 10 (or 1000) |
| Sum of all weights \(= 147\) | M1 | For 147 (or 14700) or a good attempt seen or implied |
| Length \(= 15700\) metres | A1 | For 15700 metres (or 15700 m or 157 hundred metres or 15.7 km). But \(157 \Rightarrow\) M1, A0 |
# Question 7:
## Part (a)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct temporary labels at $D$ and $E$ | M1 | For correct temporary labels at $D$ and $E$ (condone extras here) |
| All temporary labels correct with no extras | A1 | Answer should be on insert |
| Value 38 at $J$ | M1 | |
| All permanent labels correct | A1 | |
| Correct order of assigning permanent labels: $A, B, C, D, G, E, F, H, J$ | B1 | |
| Shortest route: $A-B-G-E$, Length $= 900$ | B1 | For correct route and length; accept route reversed and accept length $= 9$ |
| Shortest route: $A-C-D-F-H-J$, Length $= 3800$ | B1 | For correct route and length; accept route reversed and accept length $= 38$ |
## Part (a)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Length: 4700 metres | B1 | For 47 or 4700; follow through from (i) if possible |
| $E-G-B-A-C-D-F-H-J$ | M1 | For $E-G-B-A$, or reversed, as part of a longer route |
| | M1 | For $A-C-D-F-H-J$, or reversed, as part of a longer route |
| | A1 | For whole route correct |
## Part (a)(iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $G-B-A-C-D-F-H$; $E$ and $J$ will be left out (either is sufficient) | M1 | For identifying that route will not visit every vertex |
| | A1 | May be implied |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Odd nodes are $A, C, D, E, F, G$ | | |
| Need to pair $C, D, F, G$ in the shortest way | M1 | For trying to pair $C, D, F, G$ (and no others) |
| $CD = 3$ and $FG = 7 \Rightarrow 10$; $(CF=10,\ DG=11$ and $CG=8,\ DF=7)$ | A1 | For $CD$, $FG$ or 10 (or 1000) |
| Sum of all weights $= 147$ | M1 | For 147 (or 14700) or a good attempt seen or implied |
| Length $= 15700$ metres | A1 | For 15700 metres (or 15700 m or 157 hundred metres or 15.7 km). But $157 \Rightarrow$ M1, A0 |7 [Answer this question on the insert provided.]\\
The network below represents a simplified map of the centre of a small town. The arcs represent roads and the weights on the arcs represent distances, in units of 100 metres.\\
\includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-06_725_1259_495_443}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest route from $A$ to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. State the shortest route from $A$ to $E$ and the shortest route from $A$ to $J$, and give their lengths. [7]
\item The shortest route from $E$ to $J$ that passes through every vertex can be treated as being made up of two parts, one from $E$ to $A$ and the other from $A$ to $J$. Use your answers to part (i) to write down the length of the shortest such route. List the vertices in the order that they are visited in travelling from $E$ to $J$ using this route.
\item Explain why a similar approach to that used in parts (a)(i) and (a)(ii) would not give the shortest route between $G$ and $H$ that passes through every vertex.
\end{enumerate}\item By considering pairings of odd nodes, find the length of the shortest route that starts at $A$ and ends at $E$ and uses every arc at least once.
\section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS}
Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education
MATHEMATICS\\
4736\\
Decision Mathematics 1\\
INSERT for Questions 4 and 7\\
Wednesday
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2005 Q7 [17]}}