| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Session | Specimen |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with directed arcs |
| Difficulty | Moderate -0.3 This is a standard Further Maths Decision 1 question testing routine application of Dijkstra's and Floyd's algorithms with directed arcs. While it requires careful bookkeeping through multiple iterations and understanding of when each algorithm applies, it involves no novel problem-solving—just methodical execution of learned procedures. The conceptual parts (a) and (e) test basic understanding rather than deep insight. Slightly easier than average A-level due to its algorithmic, step-by-step nature. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Yes, Dijkstra's algorithm can be applied to either a directed or undirected network | B1 | cao (must include mention of 'directed' network) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Initial tables: distance \(\begin{bmatrix} - & 5 & 11 & 8 \\ 5 & - & 3 & 2 \\ 11 & 3 & - & 4 \\ 8 & \infty & 4 & - \end{bmatrix}\), route \(\begin{bmatrix} A & B & C & D \\ A & B & C & D \\ A & B & C & D \\ A & B & C & D \end{bmatrix}\) | ||
| 1st iteration: distance row 4 col 2 becomes \([13]\), route row 4 col 2 becomes \([A]\) | M1 | No change in first row and first column of both tables with at least one value in distance table reduced and one value in route table changed |
| A1 | cao | |
| 2nd iteration: distance \(\begin{bmatrix} - & 5 & [8] & [7] \\ 5 & - & 3 & 2 \\ [8] & 3 & - & 4 \\ 8 & 13 & 4 & - \end{bmatrix}\), route \(\begin{bmatrix} A & B & [B] & [B] \\ A & B & C & D \\ [B] & B & C & D \\ A & A & C & D \end{bmatrix}\) | M1 | No change in second row and second column of both tables with at least two values in distance table reduced and two values in route table changed |
| A1ft | Correct second iteration following through from candidate's first iteration | |
| 3rd iteration: distance \(\begin{bmatrix} - & 5 & 8 & 7 \\ 5 & - & 3 & 2 \\ 8 & 3 & - & 4 \\ 8 & [7] & 4 & - \end{bmatrix}\), route \(\begin{bmatrix} A & B & B & B \\ A & B & C & D \\ B & B & C & D \\ A & [C] & C & D \end{bmatrix}\) | M1 | No change in third row and third column of both tables with at least one value in distance table reduced and one value in route table changed |
| A1ft | Correct third iteration following through from candidate's second iteration | |
| 4th iteration: no changes therefore optimal | A1 | cao (no change after fourth iteration) – all previous marks must have been awarded |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Start at D (4th row) and read across to B (2nd column), there is a C there, so route starts DC. Look at C row, B column and you see B | B1 | Clear indication of how the final route table can be used to get from D to B (must mention correct rows and columns in reasoning) |
| The route is therefore DCB | B1 | Completely correct argument + correct route (DCB) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(D-C-B-A-\mathbf{B}-D\) | M1 | Deduce correctly their minimum route from their final distance table (dependent on all M marks in (a)); must begin and end at D |
| Length 19 (miles) | A1 | cao (length of 19) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Dijkstra's algorithm finds the shortest distances from one vertex to all the others | B1 | cao – must use correct language 'one vertex to all other vertices' |
| Floyd's algorithm finds the shortest distance between every pair of vertices | B1 | cao – must use correct language 'every pair of vertices' |
# Question 4:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Yes, Dijkstra's algorithm can be applied to either a directed or undirected network | B1 | cao (must include mention of 'directed' network) |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Initial tables: distance $\begin{bmatrix} - & 5 & 11 & 8 \\ 5 & - & 3 & 2 \\ 11 & 3 & - & 4 \\ 8 & \infty & 4 & - \end{bmatrix}$, route $\begin{bmatrix} A & B & C & D \\ A & B & C & D \\ A & B & C & D \\ A & B & C & D \end{bmatrix}$ | | |
| 1st iteration: distance row 4 col 2 becomes $[13]$, route row 4 col 2 becomes $[A]$ | M1 | No change in first row and first column of both tables with at least one value in distance table reduced and one value in route table changed |
| | A1 | cao |
| 2nd iteration: distance $\begin{bmatrix} - & 5 & [8] & [7] \\ 5 & - & 3 & 2 \\ [8] & 3 & - & 4 \\ 8 & 13 & 4 & - \end{bmatrix}$, route $\begin{bmatrix} A & B & [B] & [B] \\ A & B & C & D \\ [B] & B & C & D \\ A & A & C & D \end{bmatrix}$ | M1 | No change in second row and second column of both tables with at least two values in distance table reduced and two values in route table changed |
| | A1ft | Correct second iteration following through from candidate's first iteration |
| 3rd iteration: distance $\begin{bmatrix} - & 5 & 8 & 7 \\ 5 & - & 3 & 2 \\ 8 & 3 & - & 4 \\ 8 & [7] & 4 & - \end{bmatrix}$, route $\begin{bmatrix} A & B & B & B \\ A & B & C & D \\ B & B & C & D \\ A & [C] & C & D \end{bmatrix}$ | M1 | No change in third row and third column of both tables with at least one value in distance table reduced and one value in route table changed |
| | A1ft | Correct third iteration following through from candidate's second iteration |
| 4th iteration: no changes therefore optimal | A1 | cao (no change after fourth iteration) – all previous marks must have been awarded |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Start at D (4th row) and read across to B (2nd column), there is a C there, so route starts DC. Look at C row, B column and you see B | B1 | Clear indication of how the final route table can be used to get from D to B (must mention correct rows and columns in reasoning) |
| The route is therefore DCB | B1 | Completely correct argument + correct route (DCB) |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| $D-C-B-A-\mathbf{B}-D$ | M1 | Deduce correctly their minimum route from their final distance table (dependent on all M marks in (a)); must begin and end at D |
| Length 19 (miles) | A1 | cao (length of 19) |
## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Dijkstra's algorithm finds the shortest distances from **one** vertex to **all** the others | B1 | cao – must use correct language 'one vertex to all other vertices' |
| Floyd's algorithm finds the shortest distance between **every pair** of vertices | B1 | cao – must use correct language 'every pair of vertices' |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-05_572_799_228_632}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
The network in Figure 3 shows the roads linking a depot, D, and three collection points $\mathrm { A } , \mathrm { B }$ and C . The number on each arc represents the length, in miles, of the corresponding road. The road from B to D is a one-way road, as indicated by the arrow.
\begin{enumerate}[label=(\alph*)]
\item Explain clearly if Dijkstra's algorithm can be used to find a route from D to A .
The initial distance and route tables for the network are given in the answer book.
\item Use Floyd's algorithm to find a table of least distances. You should show both the distance table and the route table after each iteration.
\item Explain how the final route table can be used to find the shortest route from D to B . State this route.
There are items to collect at $\mathrm { A } , \mathrm { B }$ and C . A van will leave D to make these collections in any order and then return to D. A minimum route is required.
Using the final distance table and the Nearest Neighbour algorithm starting at D,
\item find a minimum route and state its length.
Floyd's algorithm and Dijkstra's algorithm are applied to a network. Each will find the shortest distance between vertices of the network.
\item Describe how the results of these algorithms differ.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 Q4 [14]}}