| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2021 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Algorithmic complexity calculations |
| Difficulty | Standard +0.3 This is a straightforward Further Maths Decision question combining routine application of Dijkstra's algorithm with basic algorithmic complexity calculations. Part (a) is standard textbook application, part (b) requires simple proportion using O(n²) scaling (200²/10² × 0.082), and part (c) asks for standard limitations of Big-O notation. While Further Maths content, this represents a typical exam question with no novel problem-solving required. |
| 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 a smaller value in at least two working boxes at D, F, G, or H | M1 | 1.1b |
| All values in A, B, C and E correct; condone lack of 0 in A's working value | A1 | 1.1b |
| All values in D and F correct, working values in correct order; penalise order of labelling only once | A1 | 1.1b |
| All values in G and H correct on follow through, working values in correct order | A1ft | 1.1b |
| Shortest path from A to H: ABEFGH | A1 | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Length of shortest path from A to H is 112 | A1ft | 2.2a; follow through their final value at H only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Applying Dijkstra repeatedly to \(n\) nodes implies order is \(n(n^2) = n^3\) | B1 | 3.1b |
| \(t = 0.082\left(\dfrac{200}{10}\right)^3\) | M1 | 3.4; allow \(10/200\); allow slips e.g. 0.82 for 0.082; accept \(200/10\) squared or cubed only |
| \(= 656\) (seconds) | A1 | 2.2a; cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Order of \(n^3\) does not mean run-time is exactly proportional to \(n^3\); may suggest other terms \((n^3 + \ldots)\), or that \(n^3\) is dominant term, or order does not imply proportionality | B1 | 3.2b; do not accept only '\(n^3\) is not exact'; condone use of \(n^2\) (oe) for \(n^3\) |
# Question 6(a)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| A larger value replaced by a smaller value in at least two working boxes at D, F, G, or H | M1 | 1.1b |
| All values in A, B, C and E correct; condone lack of 0 in A's working value | A1 | 1.1b |
| All values in D and F correct, working values in correct order; penalise order of labelling only once | A1 | 1.1b |
| All values in G and H correct on follow through, working values in correct order | A1ft | 1.1b |
| Shortest path from A to H: ABEFGH | A1 | 2.2a |
# Question 6(a)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| Length of shortest path from A to H is 112 | A1ft | 2.2a; follow through their final value at H only |
# Question 6(b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Applying Dijkstra repeatedly to $n$ nodes implies order is $n(n^2) = n^3$ | B1 | 3.1b |
| $t = 0.082\left(\dfrac{200}{10}\right)^3$ | M1 | 3.4; allow $10/200$; allow slips e.g. 0.82 for 0.082; accept $200/10$ squared or cubed **only** |
| $= 656$ (seconds) | A1 | 2.2a; cao |
# Question 6(c):
| Answer | Mark | Guidance |
|--------|------|----------|
| Order of $n^3$ does not mean run-time is exactly proportional to $n^3$; may suggest other terms $(n^3 + \ldots)$, or that $n^3$ is dominant term, or order does not imply proportionality | B1 | 3.2b; do not accept only '$n^3$ is not exact'; condone use of $n^2$ (oe) for $n^3$ |
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-07_728_1465_248_301}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
In Figure 4 the weights on the arcs represent distances.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm to find the shortest path from A to H .
\item State the length of the shortest path from A to H .
One application of Dijkstra's algorithm has order $n ^ { 2 }$, where $n$ is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra's algorithm from each node of the network.
It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
\end{enumerate}\item Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.
\item Explain why your answer to part (b) can only be an approximation.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2021 Q6 [10]}}