| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| 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 start/end points—routine D1 content. Part (b) is Chinese Postman (route inspection) on a small network, requiring identification of odd vertices and pairing, but this is a textbook algorithm application with no novel problem-solving required. Slightly easier than average due to straightforward setup and small network size. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Clear method showing at least 1 update (looking at E, F, G or H) | M1 | |
| Nodes B, C, D, E labelled correctly: B=15, C=19, D=20, E=22 | A1 | |
| Nodes F, G, H labelled correctly: F=27, G=25, H=36 | A1ft | |
| Route: ADEGH | A1 | |
| Total time: 36 minutes | A1ft | (5 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Odd nodes are A, B, C, H | M1 | Method mark for identifying odd nodes |
| \(AB + CH = 15 + 25 = 40\) | A1 | |
| \(AC + BH = 19 + 22 = 41\) | A1 | |
| \(AH + BC = 36 + 22 = 58\) | A1 | |
| 40 is the shortest, repeating AB and \(CF + FG + GH\) | ||
| Shortest time \(= 167 + 40 = 207\) minutes; \(167 +\) their shortest | A1ft | Must be choosing from at least two pairings for this last mark |
# Question 3:
## Part (a)
| Clear method showing at least 1 update (looking at E, F, G or H) | M1 | |
| Nodes B, C, D, E labelled correctly: B=15, C=19, D=20, E=22 | A1 | |
| Nodes F, G, H labelled correctly: F=27, G=25, H=36 | A1ft | |
| Route: ADEGH | A1 | |
| Total time: 36 minutes | A1ft | (5 marks total) |
# Question 3(b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Odd nodes are A, B, C, H | M1 | Method mark for identifying odd nodes |
| $AB + CH = 15 + 25 = 40$ | A1 | |
| $AC + BH = 19 + 22 = 41$ | A1 | |
| $AH + BC = 36 + 22 = 58$ | A1 | |
| 40 is the shortest, repeating AB and $CF + FG + GH$ | | |
| Shortest time $= 167 + 40 = 207$ minutes; $167 +$ their shortest | A1ft | Must be choosing from at least two pairings for this last mark |
**Total: [10]** (5 marks for part b)
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{17bc9fb2-13bf-4ffa-93ac-bef170467570-4_579_1273_239_397}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
[The total weight of the network is 167]\\
Figure 3 represents a network of paths. The number on each arc gives the time, in minutes, to travel along that path.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the quickest route from A to H. State your quickest route and the time taken.\\
(5)
Kevin must walk along each path at least once and return to his starting point.
\item Use an appropriate algorithm to find the time of Kevin's quickest possible route, starting and finishing at A. You should make your method and working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2010 Q3 [10]}}