| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2022 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm application |
| Difficulty | Moderate -0.8 This is a straightforward Floyd's algorithm application from D1, requiring students to complete a distance table and identify that vertex A can be deleted. The algorithm is mechanical and well-practiced, involving systematic table updates with minimal problem-solving. Standard bookwork for this module, easier than average A-level questions overall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| A | B | C | D | E | F | G | H | |
| A | - | |||||||
| B | - | 14 | 2 | 4 | 11 | 18 | 19 | |
| C | 14 | - | 12 | 10 | 15 | 22 | 23 | |
| D | 2 | 12 | - | 2 | 9 | 16 | 17 | |
| E | 4 | 10 | 2 | - | 7 | 14 | 15 | |
| F | 11 | 15 | 9 | 7 | - | 7 | 8 | |
| G | 18 | 22 | 16 | 14 | 7 | - | 1 | |
| H | 19 | 23 | 17 | 15 | 8 | 1 | - |
| B | C | D | E | F | G | H | |
| B | - | 14 | 2 | 4 | 11 | 18 | 19 |
| C | 14 | - | 12 | 10 | 15 | 22 | 23 |
| D | 2 | 12 | - | 2 | 9 | 16 | 17 |
| E | 4 | 10 | 2 | - | 7 | 14 | 15 |
| F | 11 | 15 | 9 | 7 | - | 7 | 8 |
| G | 18 | 22 | 16 | 14 | 7 | - | 1 |
| H | 19 | 23 | 17 | 15 | 8 | 1 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied correctly – working values at each node correct | M1 | Order of labelling must be strictly increasing sequence |
| Correct final values and labels at A, B, C, D | A1 | Working values at F must be 23 21 18 in that order |
| Correct final values and labels at E, F | A1 | |
| Correct final values and labels at G, H | A1ft | |
| Dependent method mark for correct algorithm | dM1 | |
| Fully correct diagram | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| NNA: \(A - B - D - E - F - G - H - C - A\) | B1 | |
| \(7 + 2 + 2 + 7 + 7 + 1 + 23 + 8 = 57\) (km) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Prim (starting at C): CE, DE, BD, EF, FG, GH | M1 A1 | |
| RMST weight \(= 10 + 2 + 2 + 7 + 7 + 1 = 29\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(29 + 7(\text{AB}) + 8(\text{AC}) = 44\) (km) | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(44 \leqslant \text{optimal distance} \leqslant 57\) | B2, 1, 0 |
# Question 6(a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied correctly – working values at each node correct | M1 | Order of labelling must be strictly increasing sequence |
| Correct final values and labels at A, B, C, D | A1 | Working values at F must be 23 21 18 in that order |
| Correct final values and labels at E, F | A1 | |
| Correct final values and labels at G, H | A1ft | |
| Dependent method mark for correct algorithm | dM1 | |
| Fully correct diagram | A1 | |
# Question 6(b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| NNA: $A - B - D - E - F - G - H - C - A$ | B1 | |
| $7 + 2 + 2 + 7 + 7 + 1 + 23 + 8 = 57$ (km) | B1 | |
# Question 6(c)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Prim (starting at C): CE, DE, BD, EF, FG, GH | M1 A1 | |
| RMST weight $= 10 + 2 + 2 + 7 + 7 + 1 = 29$ | | |
# Question 6(c)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $29 + 7(\text{AB}) + 8(\text{AC}) = 44$ (km) | M1 A1 | |
# Question 6(d):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $44 \leqslant \text{optimal distance} \leqslant 57$ | B2, 1, 0 | |6.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{765ea64e-d4b8-4f0f-9a43-2619f9db0c18-14_1468_1779_285_143}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G & H \\
\hline
A & - & & & & & & & \\
\hline
B & & - & 14 & 2 & 4 & 11 & 18 & 19 \\
\hline
C & & 14 & - & 12 & 10 & 15 & 22 & 23 \\
\hline
D & & 2 & 12 & - & 2 & 9 & 16 & 17 \\
\hline
E & & 4 & 10 & 2 & - & 7 & 14 & 15 \\
\hline
F & & 11 & 15 & 9 & 7 & - & 7 & 8 \\
\hline
G & & 18 & 22 & 16 & 14 & 7 & - & 1 \\
\hline
H & & 19 & 23 & 17 & 15 & 8 & 1 & - \\
\hline
\end{tabular}
\end{center}
\section*{Question 6 continued}
(b) $\_\_\_\_$\\
(c)
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& B & C & D & E & F & G & H \\
\hline
B & - & 14 & 2 & 4 & 11 & 18 & 19 \\
\hline
C & 14 & - & 12 & 10 & 15 & 22 & 23 \\
\hline
D & 2 & 12 & - & 2 & 9 & 16 & 17 \\
\hline
E & 4 & 10 & 2 & - & 7 & 14 & 15 \\
\hline
F & 11 & 15 & 9 & 7 & - & 7 & 8 \\
\hline
G & 18 & 22 & 16 & 14 & 7 & - & 1 \\
\hline
H & 19 & 23 & 17 & 15 & 8 & 1 & - \\
\hline
\end{tabular}
\end{center}
\section*{Question 6 continued}
\hfill \mbox{\textit{Edexcel D1 2022 Q6 [14]}}