| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Route inspection starting and ending at same vertex |
| Difficulty | Standard +0.3 Part (a) is a standard Dijkstra's algorithm application (routine D1 content), while part (b) is a textbook route inspection problem requiring identification of odd vertices and pairing. Both are algorithmic procedures taught explicitly in D1 with minimal problem-solving insight needed. Slightly above average due to the two-part structure and need to execute algorithms carefully, but well within standard D1 exam expectations. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| (a) Route: ADGHI; Length: 48 (km) | M1 A1 A1ft A1 | (5 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| (b) Odd vertices are A and H. Attempt to find shortest route from A to H = ADGH. New length: 197 + 36 = 233. Route: e.g. ADGHGDACEDHIFHEFBA (18) | B1 M1 A1ft A1 | (4 marks) |
**(a)** Route: ADGHI; Length: 48 (km) | M1 A1 A1ft A1 | (5 marks) |
**Guidance:** M1: Smaller number replacing larger number in the working values at E or F or H or I. (generous – give bod). 1A1: All values in boxes A to E and G correct. 2A1ft: All values in boxes F, H and I correct (ft). Penalise order of labelling just once. 3A1: CAO (not ft). 4A1ft: Follow through from their I value, condone lack of units here.
**(b)** Odd vertices are A and H. Attempt to find shortest route from A to H = ADGH. New length: 197 + 36 = 233. Route: e.g. ADGHGDACEDHIFHEFBA (18) | B1 M1 A1ft A1 | (4 marks) |
**Guidance:** B1: A and H identified in some way – allow recovery from M mark. 1M1: Accept if correct path, or its length. Accept attempt if finding shortest. 1A1ft: 197 + their shortest A to H (36). 2A1: A correct route.
**Total for Q3: 9 marks**
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-3_549_1397_258_333}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 shows a network of roads. The number on each arc represents the length, in km, of that road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from A to I. State your shortest route and its length.\\
(5)
Sam has been asked to inspect the network and assess the condition of the roads. He must travel along each road at least once, starting and finishing at A .
\item Use an appropriate algorithm to determine the length of the shortest route Sam can travel. State a shortest route.\\
(4)\\
(The total weight of the network is 197 km )
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2008 Q3 [9]}}