| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2022 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm application |
| Difficulty | Moderate -0.5 This is a standard Floyd's algorithm question requiring mechanical application of the iterative procedure to update a distance matrix. While it involves multiple steps and careful arithmetic, it requires no problem-solving insight—students simply apply the learned algorithm systematically, making it easier than average for A-level but typical for Further Maths Decision module questions. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| A | B | C | D | E | F | |
| A | - | 12 | 32 | 24 | 29 | 11 |
| B | 12 | - | 17 | 8 | \(\infty\) | \(\infty\) |
| C | 32 | 17 | - | 4 | 12 | \(\infty\) |
| D | 24 | \(\infty\) | 4 | - | \(\infty\) | 13 |
| E | \(\infty\) | \(\infty\) | 12 | 18 | - | 12 |
| F | 11 | \(\infty\) | \(\infty\) | 13 | 12 | - |
| A | B | C | D | E | F | |
| A | - | 12 | 29 | 20 | 29 | 11 |
| B | 12 | - | 17 | 8 | 41 | 23 |
| C | 29 | 17 | - | 4 | 12 | 40 |
| D | 24 | 36 | 4 | - | 53 | 13 |
| E | \(\infty\) | \(\infty\) | 12 | 18 | - | 12 |
| F | 11 | 23 | 40 | 13 | 12 | - |
| A | B | C | D | E | F | |
| A | - | 12 | 24 | 20 | 23 | 11 |
| B | 12 | - | 12 | 8 | 24 | 21 |
| C | 28 | 17 | - | 4 | 12 | 17 |
| D | 24 | 21 | 4 | - | 16 | 13 |
| E | 23 | 29 | 12 | 16 | - | 12 |
| F | 11 | 23 | 17 | 13 | 12 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct five arcs from A drawn | M1 | 1.1b |
| cao no additional arcs or arrows, correct weights and arc AE directed from A to E | A1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Third iteration — no change in third row and third column with at least two values reduced correctly | M1 | 1.1b |
| Third iteration fully correct | A1 | 1.1b |
| Fourth iteration — no change in fourth row and fourth column with at least two values correctly reduced following from previous iteration | M1 | 1.1b |
| Both iterations correct (cso — no follow through from incorrect third iteration) | A1 | 1.1b |
| Answer | Marks |
|---|---|
| \(\begin{array}{c | cccccc} & A & B & C & D & E & F \\ \hline A & - & 12 & 29 & 20 & 29 & 11 \\ B & 12 & - & 17 & 8 & \mathbf{29} & 23 \\ C & 29 & 17 & - & 4 & 12 & 40 \\ D & 24 & \mathbf{21} & 4 & - & \mathbf{16} & 13 \\ E & \mathbf{41} & \mathbf{29} & 12 & \mathbf{16} & - & 12 \\ F & 11 & 23 & 40 & 13 & 12 & - \end{array}\) |
| Answer | Marks |
|---|---|
| \(\begin{array}{c | cccccc} & A & B & C & D & E & F \\ \hline A & - & 12 & \mathbf{24} & 20 & 29 & 11 \\ B & 12 & - & \mathbf{12} & 8 & \mathbf{24} & \mathbf{21} \\ C & \mathbf{28} & 17 & - & 4 & 12 & \mathbf{17} \\ D & 24 & 21 & 4 & - & 16 & 13 \\ E & \mathbf{40} & 29 & 12 & 16 & - & 12 \\ F & 11 & 23 & \mathbf{17} & 13 & 12 & - \end{array}\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Either cycle correct (must include returning to E), nodes in correct order | M1 | 3.4 |
| \(E - C - D - F - A - B - E\), Length \(= 76\) | A1 | 1.1b |
| \(E - F - A - B - D - C - E\), Length \(= 59\) | A1 | 1.1b |
| The cycle that begins \(E - F - \ldots\) is the better upper bound as the value is the smaller of the two | A1 | 2.4 |
## Question 3:
### Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct five arcs from A drawn | M1 | 1.1b |
| cao no additional arcs or arrows, correct weights and arc AE directed from A to E | A1 | 1.1b |
### Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Third iteration — no change in third row and third column with at least two values reduced correctly | M1 | 1.1b |
| Third iteration fully correct | A1 | 1.1b |
| Fourth iteration — no change in fourth row and fourth column with at least two values correctly reduced following from previous iteration | M1 | 1.1b |
| Both iterations correct (cso — no follow through from incorrect third iteration) | A1 | 1.1b |
**Third iteration matrix (bold = changed):**
$\begin{array}{c|cccccc} & A & B & C & D & E & F \\ \hline A & - & 12 & 29 & 20 & 29 & 11 \\ B & 12 & - & 17 & 8 & \mathbf{29} & 23 \\ C & 29 & 17 & - & 4 & 12 & 40 \\ D & 24 & \mathbf{21} & 4 & - & \mathbf{16} & 13 \\ E & \mathbf{41} & \mathbf{29} & 12 & \mathbf{16} & - & 12 \\ F & 11 & 23 & 40 & 13 & 12 & - \end{array}$
**Fourth iteration matrix (bold = changed):**
$\begin{array}{c|cccccc} & A & B & C & D & E & F \\ \hline A & - & 12 & \mathbf{24} & 20 & 29 & 11 \\ B & 12 & - & \mathbf{12} & 8 & \mathbf{24} & \mathbf{21} \\ C & \mathbf{28} & 17 & - & 4 & 12 & \mathbf{17} \\ D & 24 & 21 & 4 & - & 16 & 13 \\ E & \mathbf{40} & 29 & 12 & 16 & - & 12 \\ F & 11 & 23 & \mathbf{17} & 13 & 12 & - \end{array}$
### Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Either cycle correct (must include returning to E), nodes in correct order | M1 | 3.4 |
| $E - C - D - F - A - B - E$, Length $= 76$ | A1 | 1.1b |
| $E - F - A - B - D - C - E$, Length $= 59$ | A1 | 1.1b |
| The cycle that begins $E - F - \ldots$ is the better upper bound as the value is the smaller of the two | A1 | 2.4 |
---3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one-way only.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 12 & 32 & 24 & 29 & 11 \\
\hline
B & 12 & - & 17 & 8 & $\infty$ & $\infty$ \\
\hline
C & 32 & 17 & - & 4 & 12 & $\infty$ \\
\hline
D & 24 & $\infty$ & 4 & - & $\infty$ & 13 \\
\hline
E & $\infty$ & $\infty$ & 12 & 18 & - & 12 \\
\hline
F & 11 & $\infty$ & $\infty$ & 13 & 12 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
\begin{enumerate}[label=(\alph*)]
\item By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book.
Floyd's algorithm is to be used to find the complete network of shortest distances between the six classrooms.
The distance matrix after two iterations of Floyd's algorithm is shown in Table 2.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 12 & 29 & 20 & 29 & 11 \\
\hline
B & 12 & - & 17 & 8 & 41 & 23 \\
\hline
C & 29 & 17 & - & 4 & 12 & 40 \\
\hline
D & 24 & 36 & 4 & - & 53 & 13 \\
\hline
E & $\infty$ & $\infty$ & 12 & 18 & - & 12 \\
\hline
F & 11 & 23 & 40 & 13 & 12 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}
\item Perform the next two iterations of Floyd's algorithm that follow from Table 2. You should show the distance matrix after each iteration.
The final distance matrix after completion of Floyd's algorithm is shown in Table 3.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 12 & 24 & 20 & 23 & 11 \\
\hline
B & 12 & - & 12 & 8 & 24 & 21 \\
\hline
C & 28 & 17 & - & 4 & 12 & 17 \\
\hline
D & 24 & 21 & 4 & - & 16 & 13 \\
\hline
E & 23 & 29 & 12 & 16 & - & 12 \\
\hline
F & 11 & 23 & 17 & 13 & 12 & - \\
\hline
\end{tabular}
\end{center}
\section*{Table 3}
Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.
\item \begin{enumerate}[label=(\roman*)]
\item Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.
\item Find the length of each of the two cycles.
\item State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka's route.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2022 Q3 [10]}}