| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Basic Dijkstra's algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward application of Dijkstra's algorithm, a standard D1 procedure that students practice extensively. It requires careful execution of a learned algorithm rather than problem-solving or insight, making it easier than average A-level maths questions which typically involve more conceptual understanding or multi-step reasoning. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Route: A E H I | 5A1 | Diagram with correct boxes at A, B, D, F and working shown |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Shortest distance from A to G is 28 km | B1ft | (1) |
**Part (a)**
Answer: Route: A E H I | 5A1 | Diagram with correct boxes at A, B, D, F and working shown | M1; 1A1; 2A1ft; 3A1ft; 4A1ft | (7) | 1M1: Small replacing big in the working values at C or F or G or I. 1A1: Everything correct in boxes at A, B, D and F. 2A1ft: ft boxes at E and C handled correctly but penalise order of labelling only once. 3A1ft: ft boxes at G and H handled correctly but penalise order of labelling only once. 4A1ft: ft boxes at I handled correctly but penalise order of labelling only once.
**Part (b)**
Answer: Shortest distance from A to G is 28 km | B1ft | (1) | 1B1ft: ft their final label at G condone lack of km.
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-6_899_1493_262_285}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 represents a network of roads. The number on each arc gives the length, in km , of that road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.\\
(6)
\item State the shortest distance from A to G .\\
(1)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q6 [7]}}