Question 3 - A-Level Maths

Edexcel FD1 2020 June — Question 3 9 marks

Exam Board	Edexcel
Module	FD1 (Further Decision 1)
Year	2020
Session	June
Marks	9
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 application from Further Maths Decision 1, requiring methodical execution of a learned procedure. Part (a) involves setting up initial matrices from a diagram (routine), while part (b) requires two iterations of the algorithm following given intermediate matrices. Though it's a Further Maths topic and requires careful bookkeeping across multiple matrices, it's purely algorithmic with no problem-solving or insight required—students either know the procedure or don't. This places it slightly below average difficulty for A-level maths overall.
Spec	7.04a Shortest path: Dijkstra's algorithm

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-04_387_519_214_774} \captionsetup{labelformat=empty} \caption{Figure 2}

\end{figure} Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.

Set up initial time and route matrices. The matrices after two iterations of Floyd's algorithm are shown below. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Time matrix}
\cline { 2 - 6 } \multicolumn{1}{c|}{} A B C D E
A - 8 4 7 18
B 8 - 3 15 10
C 4 3 - 11 6
D 7 15 1 - 1
E 18 10 6 1 -
\end{table} \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Route matrix}
\cline { 2 - 6 } \multicolumn{1}{c|}{} A B C D E
A A B C D B
B A B C A E
C A B C A E
D A A C D E
E B B C D E
\end{table}
Perform the next two iterations of Floyd's algorithm that follow from the tables above. You should show the time and route matrices after each iteration. The final time matrix after completion of Floyd's algorithm is shown below. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Final time matrix}
\cline { 2 - 6 } \multicolumn{1}{c|}{} A B C D E
A - 7 4 7 8
B 7 - 3 10 9
C 4 3 - 7 6
D 5 4 1 - 1
E 6 5 2 1 -
\end{table}
1. Use the nearest neighbour algorithm, starting at A , to find a Hamiltonian cycle in the complete network of shortest times.
2. Find the time taken for this cycle.
3. Interpret the cycle in terms of the actual villages visited.

Show mark scheme Show mark scheme source

Question 3:

Part (a)

Answer	Marks	Guidance
Answer	Mark	Guidance
Correct time matrix (initial, with \(\infty\) entries)	B1	Correct time matrix
Correct route matrix (all entries matching diagonal labels)	B1	Correct route matrix

Part (b)

Answer	Marks	Guidance
Answer	Mark	Guidance
First iteration: correct updated time matrix with C pivot	M1	No change in third row/column of both matrices, at least one value in time matrix reduced correctly, one value in route matrix changed to C
First iteration route matrix correct	A1	CAO
Second iteration: correct updated time matrix with D pivot	M1	No change in fourth row/column, at least one value reduced correctly (follow through first iteration), one value in route matrix changed to D
Second iteration route matrix correct	A1	CAO

Part (c)(i)

Answer	Marks	Guidance
Answer	Mark	Guidance
NNA: \(A - C - B - E - D - A\)	B1	CAO

Part (c)(ii)

Answer	Marks	Guidance
Answer	Mark	Guidance
\(4 + 3 + 9 + 1 + 5 = 22\) minutes	dB1	CAO – not from \(A-C-D-E-B-A\)

Part (c)(iii)

Answer	Marks	Guidance
Answer	Mark	Guidance
\(A - C - B - C - E - D - C - A\)	B1	CAO

# Question 3:

## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct time matrix (initial, with $\infty$ entries) | B1 | Correct time matrix |
| Correct route matrix (all entries matching diagonal labels) | B1 | Correct route matrix |

## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| First iteration: correct updated time matrix with C pivot | M1 | No change in third row/column of both matrices, at least one value in time matrix reduced correctly, one value in route matrix changed to C |
| First iteration route matrix correct | A1 | CAO |
| Second iteration: correct updated time matrix with D pivot | M1 | No change in fourth row/column, at least one value reduced correctly (follow through first iteration), one value in route matrix changed to D |
| Second iteration route matrix correct | A1 | CAO |

## Part (c)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| NNA: $A - C - B - E - D - A$ | B1 | CAO |

## Part (c)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $4 + 3 + 9 + 1 + 5 = 22$ minutes | dB1 | CAO – not from $A-C-D-E-B-A$ |

## Part (c)(iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| $A - C - B - C - E - D - C - A$ | B1 | CAO |

---

Show LaTeX source

3.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-04_387_519_214_774}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}

Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc.

Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.
\begin{enumerate}[label=(\alph*)]
\item Set up initial time and route matrices.

The matrices after two iterations of Floyd's algorithm are shown below.

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Time matrix}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & A & B & C & D & E \\
\hline
A & - & 8 & 4 & 7 & 18 \\
\hline
B & 8 & - & 3 & 15 & 10 \\
\hline
C & 4 & 3 & - & 11 & 6 \\
\hline
D & 7 & 15 & 1 & - & 1 \\
\hline
E & 18 & 10 & 6 & 1 & - \\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Route matrix}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & A & B & C & D & E \\
\hline
A & A & B & C & D & B \\
\hline
B & A & B & C & A & E \\
\hline
C & A & B & C & A & E \\
\hline
D & A & A & C & D & E \\
\hline
E & B & B & C & D & E \\
\hline
\end{tabular}
\end{center}
\end{table}
\item Perform the next two iterations of Floyd's algorithm that follow from the tables above. You should show the time and route matrices after each iteration.

The final time matrix after completion of Floyd's algorithm is shown below.

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Final time matrix}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & A & B & C & D & E \\
\hline
A & - & 7 & 4 & 7 & 8 \\
\hline
B & 7 & - & 3 & 10 & 9 \\
\hline
C & 4 & 3 & - & 7 & 6 \\
\hline
D & 5 & 4 & 1 & - & 1 \\
\hline
E & 6 & 5 & 2 & 1 & - \\
\hline
\end{tabular}
\end{center}
\end{table}
\item \begin{enumerate}[label=(\roman*)]
\item Use the nearest neighbour algorithm, starting at A , to find a Hamiltonian cycle in the complete network of shortest times.
\item Find the time taken for this cycle.
\item Interpret the cycle in terms of the actual villages visited.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 2020 Q3 [9]}}

This paper (7 questions)

View full paper

Q1 6 Q2 15 Q3 9 Q4 10 Q5 7 Q6 11 Q7 17

\cline { 2 - 6 } \multicolumn{1}{c\|}{}	A	B	C	D	E
A	-	8	4	7	18
B	8	-	3	15	10
C	4	3	-	11	6
D	7	15	1	-	1
E	18	10	6	1	-