| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2019 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Moderate -0.8 This is a standard algorithmic application question from D1. Part (a) requires mechanical application of Prim's algorithm with clear bookkeeping, part (b) tests understanding of uniqueness conditions (checking for repeated edge weights), and part (c) is routine Dijkstra's algorithm. All three parts are textbook exercises requiring careful execution but no problem-solving insight or novel thinking. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | H | J | |
| A | - | 3 | 8 | 5 | - | - | - | - | - |
| B | 3 | - | 4 | - | - | - | - | - | - |
| C | 8 | 4 | - | - | 9 | 4 | - | - | - |
| D | 5 | - | - | - | - | 7 | 4 | 9 | - |
| E | - | - | 9 | - | - | 4 | - | - | 7 |
| F | - | - | 4 | 7 | 4 | - | - | 8 | 13 |
| G | - | - | - | 4 | - | - | - | 4 | - |
| H | - | - | - | 9 | - | 8 | 4 | - | 7 |
| J | - | - | - | - | 7 | 13 | - | 7 | - |
3.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G & H & J \\
\hline
A & - & 3 & 8 & 5 & - & - & - & - & - \\
\hline
B & 3 & - & 4 & - & - & - & - & - & - \\
\hline
C & 8 & 4 & - & - & 9 & 4 & - & - & - \\
\hline
D & 5 & - & - & - & - & 7 & 4 & 9 & - \\
\hline
E & - & - & 9 & - & - & 4 & - & - & 7 \\
\hline
F & - & - & 4 & 7 & 4 & - & - & 8 & 13 \\
\hline
G & - & - & - & 4 & - & - & - & 4 & - \\
\hline
H & - & - & - & 9 & - & 8 & 4 & - & 7 \\
\hline
J & - & - & - & - & 7 & 13 & - & 7 & - \\
\hline
\end{tabular}
\end{center}
The table above shows the lengths, in metres, of the paths between nine vertices, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$, G, H and J.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at A , to find a minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges and state its weight. Draw your minimum spanning tree using the vertices in the answer book.
\item State whether your minimum spanning tree is unique. Justify your answer.
\item Use Dijkstra's algorithm to find the length of the shortest path from A to J.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2019 Q3 [11]}}