| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 8 |
| 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. Part (a) requires mechanical execution of the algorithm, and part (b) is trivial once (a) is complete since H is on the path to G. No problem-solving insight needed—pure algorithmic recall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied to network with working values shown at nodes S, A, B, C, D, E, F, G, H | M1 | A larger value replaced by a smaller value at least once in working values at C, E, F, G or H |
| All values at S, A, B, D and C correct; working values at C in correct order | A1 (SABDC) | Condone lack of 0 in S's working value |
| All values at F and E correct; working values in correct order; F and E labelled after S, A, B, D, C | A1 (FE) | Penalise order of labelling only once per question |
| All values at H and G correct on follow through; working values in correct order | A1ft (HG) | H and G labelled in that order; H labelled after all other nodes (excluding G) |
| Shortest distance: 23 (km) | A1ft | Follow through their final value at G (condone lack of units) |
| Shortest route: \(S - A - C - F - G\) | A1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Shortest distance: 20 (km) | B1ft | Follow through their final value at H (condone lack of units) |
| Shortest route: \(S - A - C - F - E - H\) | B1 | CAO |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied to network with working values shown at nodes S, A, B, C, D, E, F, G, H | M1 | A larger value replaced by a smaller value at least once in working values at C, E, F, G or H |
| All values at S, A, B, D and C correct; working values at C in correct order | A1 (SABDC) | Condone lack of 0 in S's working value |
| All values at F and E correct; working values in correct order; F and E labelled after S, A, B, D, C | A1 (FE) | Penalise order of labelling only once per question |
| All values at H and G correct on follow through; working values in correct order | A1ft (HG) | H and G labelled in that order; H labelled after all other nodes (excluding G) |
| Shortest distance: 23 (km) | A1ft | Follow through their final value at G (condone lack of units) |
| Shortest route: $S - A - C - F - G$ | A1 | CAO |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Shortest distance: 20 (km) | B1ft | Follow through their final value at H (condone lack of units) |
| Shortest route: $S - A - C - F - E - H$ | B1 | CAO |
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-2_686_1408_342_333}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents a network of roads. The number on each arc gives the length, in km , of the corresponding road.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest distance from S to G . State the shortest route.
\item State both the shortest distance and the shortest route from S to H .
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q1 [8]}}