Further Mathematics · Pearson Edexcel 9FM0 · Option D1 · Topic 2

Algorithms on graphs

Minimum spanning trees with Kruskal's and Prim's algorithms, and shortest paths with Dijkstra's and Floyd's algorithms.

3 sub-topics
2 in Year 12, 1 in Year 13
41 practice questions
3 animated lessons

Practice questions (41) Lessons Worksheets All Edexcel Further Mathematics topics

What the specification says

Every sub-topic Pearson Edexcel can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

2.1Minimum spanning treesY12
2.2Dijkstra's algorithmY12
2.2Floyd's algorithmY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 41 questions in this topic, free, no account needed.

Algorithms on graphs

Easy

Minimum spanning trees · Year 12 · 1 mark

A connected network has 10 vertices. How many edges does a minimum spanning tree of it have?
(1)

Show worked solutionHide worked solution

A tree on $n$ vertices always has $n - 1$ edges. $B$ : 9

Total1

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question

Algorithms on graphs

Medium

Minimum spanning trees · Year 12 · 5 marks

Figure 1 shows a network of paths between seven buildings. The numbers are lengths in metres.

Figure 1

(a)
Use Kruskal's algorithm to find a minimum spanning tree, listing the arcs in the order you select them.
(3)
(b)
State the weight of the minimum spanning tree.
(1)
(c)
Explain why Prim's algorithm would give a tree of the same weight.
(1)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)3 marks

Take arcs in order of weight, rejecting any that would form a cycle.
AD (4), DF (4), CF (5), BD (7), BE (10), FG (12)

Part (b)1 mark

$42\text{ m}$

Part (c)1 mark

Both algorithms find a minimum spanning tree, and every minimum spanning tree has the same total weight.

Total5

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question

Algorithms on graphs

Not needed for Year 12Hard

Floyd's algorithm · Year 13 · 4 marks

The table shows the direct distances between four towns; the distance from the town in the row to the town in the column, with ∞ where there is no direct road. Rows and columns are in the order A, B, C, D.

\begin{pmatrix} 0 & 5 & \infty & \infty \\ 8 & 0 & 5 & 5 \\ 3 & \infty & 0 & \infty \\ \infty & \infty & 4 & 0 \end{pmatrix}

(a)
Write down the distance table after the first iteration of Floyd's algorithm.
(2)
(b)
After the final iteration, find the shortest distance from $C$ to $B$ and the route.
(2)

Show worked solutionHide worked solution

Part (a)2 marks

Allow routes through $A$ : $d(\mathrm{i}, j)$ ${}= \min (d(\mathrm{i}, j), d(\mathrm{i}, A) + d(A, j))$ . $\begin{pmatrix} 0 & 5 & \infty & \infty \\ 8 & 0 & 5 & 5 \\ 3 & 8 & 0 & \infty \\ \infty & \infty & 4 & 0 \end{pmatrix}$

Part (b)2 marks

$8$
$CAB$

Total4

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question