| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2023 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Algorithmic complexity calculations |
| Difficulty | Standard +0.3 This is a straightforward two-part question: (a) apply Dijkstra's algorithm mechanically to a small network (standard procedure), and (b) use simple proportion with O(n²) complexity (9000²/9² × 0.0312 seconds, then convert units). Both parts are routine algorithmic applications with no problem-solving insight required, making it slightly easier than average. |
| Spec | 7.03f Worst case complexity: T(n) as function of problem size7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A larger value replaced by smaller value in working values at two of C, D, E, F, G, H or J | M1 | |
| All values in A, B, C, D correct | A1 | Condone lack of 0 in A's working value |
| All values G, E, H correct with working values in correct order | A1 | Penalise order of labelling once per question; note 65 61 80 acceptable, but 80 65 61 scores A0 |
| All values in F and J correct on follow through, working values in correct order | A1ft | Follow through from candidate's final values for nodes attached to F |
| Shortest path from A to J is ABCEHJ | A1 | CAO - not path from J to A |
| Length of shortest path is 100 | A1ft | Follow through their final value at J only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(0.0312 \times \left(\dfrac{9000}{9}\right)^2\) | M1 | Complete correct method; allow reciprocal e.g. \(0.0312 \times \left(\dfrac{9}{9000}\right)^2\); allow slips in values; if anything other than squared e.g. \(n^3\) then M0 |
| \(= 31200\) seconds therefore \(520\) minutes | A1 | CAO - exact value of 520 must be stated; condone lack of units but if present must be correct |
# Question 3:
## Part (a)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| A larger value replaced by smaller value in working values at two of C, D, E, F, G, H or J | M1 | |
| All values in A, B, C, D correct | A1 | Condone lack of 0 in A's working value |
| All values G, E, H correct with working values in correct order | A1 | Penalise order of labelling once per question; note 65 61 80 acceptable, but 80 65 61 scores A0 |
| All values in F and J correct on follow through, working values in correct order | A1ft | Follow through from candidate's final values for nodes attached to F |
| Shortest path from A to J is ABCEHJ | A1 | CAO - not path from J to A |
| Length of shortest path is 100 | A1ft | Follow through their final value at J only |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| $0.0312 \times \left(\dfrac{9000}{9}\right)^2$ | M1 | Complete correct method; allow reciprocal e.g. $0.0312 \times \left(\dfrac{9}{9000}\right)^2$; allow slips in values; if anything other than squared e.g. $n^3$ then M0 |
| $= 31200$ seconds therefore $520$ minutes | A1 | CAO - exact value of 520 must be stated; condone lack of units but if present must be correct |3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-05_862_1460_219_299}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J.\\
The number on each edge gives the length of the corresponding edge.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm to find the shortest path from A to J.
\item State the length of the shortest path from A to J .
One application of Dijkstra's algorithm has order $n ^ { 2 }$, where $n$ is the number of nodes in the network.
It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.
\end{enumerate}\item Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2023 Q3 [8]}}