| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Moderate -0.5 Part (i) is a standard application of Dijkstra's algorithm, a routine procedure taught in D1. Part (ii) is a textbook route inspection problem requiring identification of odd vertices and pairing, which is algorithmic but involves more steps. Both parts test procedural fluency rather than problem-solving insight, making this slightly easier than average for A-level. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| Shortest distance is \(385m\) | M1 A1 A1 A1 (5) |
| Answer | Marks |
|---|---|
| Odd vertices: \(B, C, D, E\) | M1 |
| \(BC + DE = 95 + 145 = 240\) | |
| \(BD + CE = 169 + 179 = 348\) | A1 |
| \(BE + CD = 249 + 74 = 323\) | A1 (4) |
| Example: \(ABCBFHCFECECEDEDA\) | B1 |
| Length: \(124 + 4 + 240 = 1481m\) | B1 (2) |
## Part (i)
Shortest distance is $385m$ | M1 A1 A1 A1 (5)
## Part (ii)
Odd vertices: $B, C, D, E$ | M1
$BC + DE = 95 + 145 = 240$ |
$BD + CE = 169 + 179 = 348$ | A1
$BE + CD = 249 + 74 = 323$ | A1 (4)
Example: $ABCBFHCFECECEDEDA$ | B1
Length: $124 + 4 + 240 = 1481m$ | B1 (2)
---\includegraphics{figure_3}
Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.
\begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm to find the shortest distance from $A$ to $H$. [5]
\item Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at $A$, and find its length.
[The total weight of the network is 1241] [6]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2005 Q5 [11]}}