| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Route inspection starting and ending at same vertex |
| Difficulty | Moderate -0.3 Part (a) is a standard Dijkstra's algorithm application with clear instructions. Part (b) is a routine Chinese Postman problem on a network, requiring identification of odd vertices and pairing them optimally. Both are textbook algorithms with straightforward execution, though the multi-part structure and need to apply two different algorithms places it slightly below average difficulty for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied correctly to network, working values and order of permanent labelling shown | M1 A1 A1 | Correct working values; Correct order of permanent labelling |
| (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Shortest route \(ABFEHI\), length 22 km | B1 B1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Odd vertices \(A\) and \(I\) only, shortest route between them needs to be repeated, hence repeat | M1 | |
| \(AB, BF, FE, EH, HI\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| e.g. \(\underline{AB}\underline{FB}\underline{EF}GI\underline{FE}\underline{HI}\underline{HE}CDAC\underline{BA}\) | A1 | (3) |
| \(91 + 22 = 113\) km | M1 A1 | (2) |
| (Marks 10) |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied correctly to network, working values and order of permanent labelling shown | M1 A1 A1 | Correct working values; Correct order of permanent labelling |
| | **(3)** | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Shortest route $ABFEHI$, length 22 km | B1 B1 | **(2)** |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Odd vertices $A$ and $I$ only, shortest route between them needs to be repeated, hence repeat | M1 | |
| $AB, BF, FE, EH, HI$ | A1 | |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| e.g. $\underline{AB}\underline{FB}\underline{EF}GI\underline{FE}\underline{HI}\underline{HE}CDAC\underline{BA}$ | A1 | **(3)** |
| $91 + 22 = 113$ km | M1 A1 | **(2)** |
| | **(Marks 10)** | |
---\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from $A$ to $I$. Show all necessary working in the boxes in the answer booklet and state your shortest route and its length.\\
(5)
The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at $A$.
\item \begin{enumerate}[label=(\roman*)]
\item Use an appropriate algorithm to find which paths will be covered twice and state these paths.
\item Find a route of minimum length.
\item Find the total length of this shortest route.\\
(5)
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q4 [10]}}