| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Standard +0.8 This is a substantial multi-part question combining Dijkstra's algorithm with Chinese Postman problem variations. Part (i) is standard Dijkstra execution (routine for D1), but parts (ii) and (iii) require understanding of Eulerian paths, identifying odd-degree vertices, finding minimum pairings, and adapting the Chinese Postman algorithm for different start/end points—this demands genuine problem-solving and synthesis of multiple algorithms beyond rote application. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Dijkstra's algorithm applied (diagram on insert sheet) | M1 | For using Dijkstra's algorithm — updating at \(E\) and \(F\) (even if incomplete) |
| All permanent labels correct | A1 | |
| Valid order of assigning permanent labels | B1 | |
| Vertex \(B\ C\ D\ E\ F\ G\); Length \(6\ 8\ 16\ 14\ 19\ 22\) | B1 | For copying their permanent labels, or correct values |
| \(A-C-E-G\) | B1 | Correct answer only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The only odd nodes are \(A\) and \(F\); shortest path from \(A\) to \(F\) has length 19 km | M1 | For identifying \(A\) and \(F\) and value 19 or their 19 |
| \(120 + 19 = 139\) km | M1, A1 | M1 for \(120 +\) their 19; A1 for 139 (cao) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Need \(A\) and \(G\) odd and all other nodes even; need to connect \(F\) to \(G = 10\) km; \(120 + 10 = 130\) km | M1 | For identifying \(F\) and \(G\) or value 10 as only extra |
| \(= 130\) km | A1 | For 130 (cao) |
# Question 4:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Dijkstra's algorithm applied (diagram on insert sheet) | M1 | For using Dijkstra's algorithm — updating at $E$ and $F$ (even if incomplete) |
| All permanent labels correct | A1 | |
| Valid order of assigning permanent labels | B1 | |
| Vertex $B\ C\ D\ E\ F\ G$; Length $6\ 8\ 16\ 14\ 19\ 22$ | B1 | For copying their permanent labels, or correct values |
| $A-C-E-G$ | B1 | Correct answer only |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| The only odd nodes are $A$ and $F$; shortest path from $A$ to $F$ has length 19 km | M1 | For identifying $A$ and $F$ and value 19 or their 19 |
| $120 + 19 = 139$ km | M1, A1 | M1 for $120 +$ their 19; A1 for 139 (cao) |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Need $A$ and $G$ odd and all other nodes even; need to connect $F$ to $G = 10$ km; $120 + 10 = 130$ km | M1 | For identifying $F$ and $G$ or value 10 as only extra |
| $= 130$ km | A1 | For 130 (cao) |
---4 [Answer this question on the insert provided.]\\
\includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-3_918_1242_351_443}
In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the lengths of roads in kilometres.\\
(i) Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest path 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. Find the route of the shortest path from $A$ to $G$.
The total weight of the arcs is 120 kilometres.\\
(ii) By using an appropriate algorithm, find the length of a shortest route that uses every road starting and ending at $A$. You should explain your method.\\
(iii) Find the length of a shortest route that uses every road starting at $A$ and ending at $G$. You should explain your method.
\hfill \mbox{\textit{OCR D1 2005 Q4 [10]}}