| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 11 |
| 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 two algorithmic procedures (Dijkstra and Route Inspection) that students practice extensively. Part (i) is routine algorithm application, part (ii) follows the standard Chinese Postman method, and part (iii) requires only observation rather than calculation. While multi-part, each component is textbook-standard with no novel problem-solving required. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct order of labelling: \(A=0\), \(B=3\), \(C=5\), \(E=6\), \(D=6\), \(F=11\) | M1 | Dijkstra's algorithm applied correctly |
| All labels correct | A1 | |
| Working values shown correctly at each node | A1 | |
| Route: \(A \to B \to C \to E \to F\) or \(A \to B \to D \to E \to F\) | A1 | |
| Weight = 11 | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total weight of all arcs = \(3+1+3+5+1+1+1+3+3+5 = 26\) | B1 | |
| Odd vertices identified as \(A\) and \(F\) | M1 | |
| Shortest path \(A\) to \(F\) = 11 | A1 | |
| Least weight closed route = \(26 + 11 = 37\) | A1 | Accept valid closed route stated e.g. \(A \to B \to C \to E \to F \to D \to B \to C \to E \to F \to \ldots\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| New least weight path \(A \to B \to E \to F\), weight \(= 3+2+3 = 8\) | B1 | |
| The graph now has all even vertices / no odd vertices, so no arcs need repeating | B1 | With arc \(BE\) added, \(B\) and \(E\) become even (degree 4 and 4), \(A\) and \(F\) remain even |
# Question 1:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct order of labelling: $A=0$, $B=3$, $C=5$, $E=6$, $D=6$, $F=11$ | M1 | Dijkstra's algorithm applied correctly |
| All labels correct | A1 | |
| Working values shown correctly at each node | A1 | |
| Route: $A \to B \to C \to E \to F$ or $A \to B \to D \to E \to F$ | A1 | |
| Weight = 11 | A1 | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total weight of all arcs = $3+1+3+5+1+1+1+3+3+5 = 26$ | B1 | |
| Odd vertices identified as $A$ and $F$ | M1 | |
| Shortest path $A$ to $F$ = 11 | A1 | |
| Least weight closed route = $26 + 11 = 37$ | A1 | Accept valid closed route stated e.g. $A \to B \to C \to E \to F \to D \to B \to C \to E \to F \to \ldots$ |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| New least weight path $A \to B \to E \to F$, weight $= 3+2+3 = 8$ | B1 | |
| The graph now has all even vertices / no odd vertices, so no arcs need repeating | B1 | With arc $BE$ added, $B$ and $E$ become even (degree 4 and 4), $A$ and $F$ remain even |
---1 Answer this question on the insert provided.
\includegraphics[max width=\textwidth, alt={}, center]{e1495f6b-c09f-46a1-a6f8-02354e28887a-02_533_1353_342_395}\\
(i) Apply Dijkstra's algorithm to the copy of this network in the insert to find the least weight path from $A$ to $F$. State the route of the path and give its weight.\\
(ii) Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. Write down a closed route that has this least weight.
An extra arc is added, joining $B$ to $E$, with weight 2 .\\
(iii) Write down the new least weight path from $A$ to $F$. Explain why the new least weight closed route, that uses every arc at least once, has no repeated arcs.
\hfill \mbox{\textit{OCR D1 2010 Q1 [11]}}