| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Moderate -0.8 This is a standard D1 question testing routine application of Dijkstra's algorithm and Prim's algorithm with no novel problem-solving required. Part (b) requires running Dijkstra twice (A to J, then J to F) which is straightforward. These are textbook algorithms applied mechanically, making this easier than average A-level maths questions which typically require more mathematical insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| A larger value replaced by smaller value at least once in working values at D, F or G | M1 | |
| All values at A, B, E, C, K correct | A1 | Condone lack of 0 in A's working value; check for 5 in working values at B |
| All values at D, J, H correct with working values in correct order | A1 | D, J, H must be labelled in that order; D labelled after A, B, E, C, K |
| All values at G and F correct, working values in correct order (follow through) | A1ft | G and F labelled in that order; G labelled after all other nodes excluding F |
| Shortest path: \(A-B-E-K-H-G-F\) | A1 | CAO (path from A to F or F to A) |
| Length of shortest path: 48 (miles) | A1ft | Follow through their final value at F |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Shortest path via J: \(A-B-E-K-J-F\) | B1 | CAO |
| Length: 49 (miles) | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Prim's algorithm: first four arcs correctly chosen in order: GF, GH, FJ, DG | M1 | If any explicit rejections seen, M1 max only |
| First seven arcs correctly chosen in order: GF, GH, FJ, DG, JK, EK, BE or GF, GH, FJ, DG, CD, JK, EK | A1 | |
| All arcs correctly stated and chosen in correct order: GF, GH, FJ, DG, JK, EK, BE, AB, CD or GF, GH, FJ, DG, CD, JK, EK, BE, AB | A1 CSO | Must be considering arcs; do not accept list of nodes only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| 80 (miles) | B1 | CAO; condone lack of units |
# Question 4:
## Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| A larger value replaced by smaller value at least once in working values at D, F or G | M1 | |
| All values at A, B, E, C, K correct | A1 | Condone lack of 0 in A's working value; check for 5 in working values at B |
| All values at D, J, H correct with working values in correct order | A1 | D, J, H must be labelled in that order; D labelled after A, B, E, C, K |
| All values at G and F correct, working values in correct order (follow through) | A1ft | G and F labelled in that order; G labelled after all other nodes excluding F |
| Shortest path: $A-B-E-K-H-G-F$ | A1 | CAO (path from A to F or F to A) |
| Length of shortest path: 48 (miles) | A1ft | Follow through their final value at F |
## Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Shortest path via J: $A-B-E-K-J-F$ | B1 | CAO |
| Length: 49 (miles) | B1 | CAO |
## Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Prim's algorithm: first four arcs correctly chosen in order: GF, GH, FJ, DG | M1 | If any explicit rejections seen, M1 max only |
| First seven arcs correctly chosen in order: GF, GH, FJ, DG, JK, EK, BE **or** GF, GH, FJ, DG, CD, JK, EK | A1 | |
| All arcs correctly stated and chosen in correct order: GF, GH, FJ, DG, JK, EK, BE, AB, CD **or** GF, GH, FJ, DG, CD, JK, EK, BE, AB | A1 CSO | Must be considering arcs; do not accept list of nodes only |
## Part (d):
| Answer/Working | Marks | Guidance |
|---|---|---|
| 80 (miles) | B1 | CAO; condone lack of units |4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{22ff916a-4ba8-4e0c-9c53-e82b0aff0b98-05_841_1201_226_431}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to F . State your path and its length.
On another day, Sarah wishes to travel from A to F via J.
\item Find a route of minimal length that goes from A to F via J and state its length.
\item Use Prim's algorithm, starting at G , to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
\item State the length, in miles, of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2016 Q4 [12]}}