D1-2 Algorithms on graphs — revision question pack

2 specification points · notes, questions, answers and worked methods

Checked against Edexcel 9FM0 section D1-2. Review basis: the qualification registry sourced from the Pearson Edexcel Level 3 Advanced GCE in Further Mathematics (9FM0) specification; registry verification recorded 17 July 2026.

How this checking works

D1-2.1 · The minimum spanning tree (minimum connector) problem. Prim's and Kruskal's algorithm.

Explanation

A spanning tree of a connected network on $n$ vertices uses every vertex and exactly $n-1$ arcs and contains no cycle; the minimum spanning tree, or minimum connector, is the one of least total weight.
Kruskal's algorithm sorts every arc into ascending order of weight and then adds arcs one at a time, rejecting any arc that would form a cycle, stopping once $n-1$ arcs are in the tree.
Prim's algorithm grows a single tree from a chosen start vertex: at each stage it adds the shortest arc joining a vertex already in the tree to a vertex not yet in it, and it never needs a cycle check because one endpoint is always outside the tree.
Prim's algorithm also runs directly on a distance matrix: delete the row of the newly connected vertex, label its column, and scan every labelled column for the smallest uncrossed entry.
Both algorithms return a tree of the same minimum weight, though the arcs may be listed in a different order and different trees of equal weight can occur when weights are repeated.

Worked example

A network has vertices $A$ , $B$ , $C$ , $D$ and arcs $AB=8$ , $AC=3$ , $AD=9$ , $BC=5$ , $BD=7$ , $CD=6$ . Use Kruskal's algorithm to find the minimum spanning tree.

1.In ascending order the arcs are $AC=3$ , $BC=5$ , $CD=6$ , $BD=7$ , $AB=8$ , $AD=9$ .
2.Accept $AC$ ; accept $BC$ ; accept $CD$ .
3.The tree now has $3=4-1$ arcs, so the algorithm stops; $BD$ , $AB$ and $AD$ would all create cycles.
4.The total weight is $3+5+6=14$ .

Answer: The minimum spanning tree uses $AC$ , $BC$ and $CD$ and has weight $14$ .

Common mistakes

Don't fall into the trap of continuing past $n-1$ arcs, or stopping before every vertex is connected.
Don't fall into the trap of sorting the arcs for Prim's algorithm, which is a Kruskal step and wastes time.
Don't fall into the trap of deleting a column instead of a row in the matrix form of Prim's algorithm, or forgetting to scan every labelled column.

Exam tip

State the arcs in the order your algorithm selects them; examiners award marks for the correct selection order as well as the final weight.

Tier 1 · Easy

1.
A network has vertices $A$ , $B$ , $C$ , $D$ , $E$ and arcs $AB=6$ , $AC=4$ , $BC=3$ , $BD=9$ , $CD=5$ , $CE=8$ , $DE=7$ . Use Kruskal's algorithm to find a minimum spanning tree, listing the arcs in the order you consider them, and state its total weight.
(5)
(Total for Question 1 is 5 marks)
2.
Explain what is meant by a spanning tree, and state how many arcs a spanning tree of a connected network with $9$ vertices must contain.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
A network has vertices $A$ to $F$ and arcs $AB=9$ , $AC=5$ , $AD=12$ , $BC=7$ , $BE=8$ , $CD=6$ , $CE=11$ , $CF=13$ , $DF=10$ , $EF=4$ . Use Prim's algorithm starting at $A$ to find a minimum spanning tree, stating the arcs in the order they are added and the total weight.
(6)
(Total for Question 1 is 6 marks)
2.
For the network with vertices $A$ to $F$ and arcs $AB=9$ , $AC=5$ , $AD=12$ , $BC=7$ , $BE=8$ , $CD=6$ , $CE=11$ , $CF=13$ , $DF=10$ , $EF=4$ , apply Kruskal's algorithm. List the arcs in the order you consider them, name any arc you reject together with the reason, and state the total weight.
(6)
(Total for Question 2 is 6 marks)
3.
A network has vertices $A$ to $G$ and arcs $AB=14$ , $AC=10$ , $AD=17$ , $BC=8$ , $BE=13$ , $CD=9$ , $CE=16$ , $CF=21$ , $DF=12$ , $EF=7$ , $EG=19$ , $FG=11$ . Apply Kruskal's algorithm and state the arcs of the minimum spanning tree and its weight.
(6)
(Total for Question 3 is 6 marks)

Tier 3 · Hard

1.
Apply Prim's algorithm starting at $A$ to the network with vertices $A$ to $G$ and arcs $AB=14$ , $AC=10$ , $AD=17$ , $BC=8$ , $BE=13$ , $CD=9$ , $CE=16$ , $CF=21$ , $DF=12$ , $EF=7$ , $EG=19$ , $FG=11$ . State the order in which the vertices join the tree, the arcs used, and verify that the weight agrees with Kruskal's answer of $57$ .
(7)
(Total for Question 1 is 7 marks)
2.
Explain why Prim's algorithm never needs to test for a cycle, whereas Kruskal's algorithm does, and describe one practical situation in which Kruskal's algorithm is the more convenient of the two.
(5)
(Total for Question 2 is 5 marks)
3.
A network on vertices $A$ to $F$ has arcs $AB=9$ , $AC=5$ , $AD=12$ , $BC=7$ , $BE=8$ , $CD=6$ , $CE=11$ , $CF=13$ , $DF=10$ , $EF=4$ . Apply Prim's algorithm starting at $D$ instead of $A$ , and explain why the resulting tree has the same weight as the tree obtained starting at $A$ .
(7)
(Total for Question 3 is 7 marks)
4.
A minimum spanning tree of a network on $6$ vertices has weight $30$ . One arc of the tree, of weight $8$ , is removed from the network because that link is closed. The shortest arc that reconnects the two parts of the tree has weight $13$ . State the weight of the new minimum spanning tree, and explain why the answer would be wrong if the replacement arc had joined two vertices in the same part.
(6)
(Total for Question 4 is 6 marks)
5.
A network on vertices $A$ to $E$ has arcs $AB=6$ , $AC=4$ , $BC=3$ , $BD=9$ , $CD=5$ , $CE=8$ , $DE=7$ . The arc $CD$ is now given the new weight $k$ , where $k>0$ . Determine the values of $k$ for which the minimum spanning tree still uses $CD$ , and state the weight of the minimum spanning tree when $k=10$ .
(7)
(Total for Question 5 is 7 marks)

D1-2.2 · Dijkstra's and Floyd's algorithm for finding the shortest path.

Explanation

Dijkstra's algorithm finds the shortest path from one start vertex to every other. Each vertex carries a box with three entries: the order of labelling, the final label, and a list of working values.
Give the start vertex final label $0$ , then repeatedly choose the smallest working value anywhere in the network, make it final,
and update every unlabelled neighbour with the sum of the new final label and the connecting arc, recording the new value only if it beats the values already there. To recover the route, trace back from the end vertex, keeping an arc $XY$ whenever the final label of $Y$ minus the final label of $X$ equals the weight of $XY$ .
Floyd's algorithm instead finds the shortest distance between every pair. Start with the distance matrix and a route matrix whose column $j$ is filled with $j$ .
On iteration $k$ compare each entry $d_{ij}$ with $d_{ik}+d_{kj}$ ; if the route through $k$ is shorter, replace $d_{ij}$ and set the route entry $r_{ij}$ to $r_{ik}$ . Iteration $k$ works on the $k$ th row and column, and after $n$ iterations the matrices are complete.

Worked example

In a network with vertices $A$ , $B$ , $C$ , $D$ and arcs $AB=4$ , $AC=7$ , $BC=2$ , $BD=8$ , $CD=3$ , use Dijkstra's algorithm from $A$ to find the shortest path to $D$ .

1. $A$ is labelled first with final label $0$ .
2.Working values become $B=4$ and $C=7$ ; the smaller is $B$ , labelled second with final label $4$ .
3.From $B$ , $C$ receives $4+2=6$ , which beats $7$ , and $D$ receives $4+8=12$ ; $C$ is labelled third with final label $6$ .
4.From $C$ , $D$ receives $6+3=9$ , which beats $12$ , so $D$ is labelled fourth with final label $9$ .

Answer: The shortest path is $ABCD$ with length $9$ , found by tracing back from $D$ through the arcs whose weights match the differences in final labels.

Common mistakes

Don't fall into the trap of overwriting a working value with a larger number instead of keeping the smallest so far.
Don't fall into the trap of updating a vertex that already has a final label.
Don't fall into the trap of changing a Floyd route entry to $k$ rather than to the current value of $r_{ik}$ .

Exam tip

Never rub out a working value: examiners award marks for the full list of working values in each box, and the crossed-out values show the algorithm was followed.

Tier 1 · Easy

1.
A network has vertices $A$ , $B$ , $C$ , $D$ , $E$ and arcs $AB=4$ , $AC=7$ , $BC=2$ , $BD=8$ , $CD=3$ , $CE=9$ , $DE=5$ . Use Dijkstra's algorithm from $A$ to find the final label of every vertex and the shortest path from $A$ to $E$ .
(6)
(Total for Question 1 is 6 marks)
2.
State what the three entries in a Dijkstra box represent, and explain why a vertex may hold more than one working value.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
A network has vertices $A$ to $F$ and arcs $AB=5$ , $AC=8$ , $BC=2$ , $BD=9$ , $CD=4$ , $CE=7$ , $DF=6$ , $EF=4$ . Use Dijkstra's algorithm from $A$ to complete every box and find the shortest route from $A$ to $F$ .
(7)
(Total for Question 1 is 7 marks)
2.
A network has vertices $A$ to $G$ and arcs $AB=6$ , $AC=9$ , $AD=11$ , $BC=4$ , $BE=12$ , $CD=5$ , $CE=8$ , $CF=14$ , $DF=10$ , $EF=3$ , $EG=15$ , $FG=7$ . Use Dijkstra's algorithm from $A$ to find the final labels of $E$ , $F$ and $G$ , listing the working values in each of those three boxes.
(7)
(Total for Question 2 is 7 marks)
3.
A network has vertices $A$ , $B$ , $C$ , $D$ with $AB=7$ , $AD=4$ , $BC=3$ , $CD=2$ and no direct arcs $AC$ or $BD$ . Write down the initial distance matrix and route matrix used by Floyd's algorithm, and carry out the first iteration.
(6)
(Total for Question 3 is 6 marks)

Tier 3 · Hard

1.
For the network on $A$ , $B$ , $C$ , $D$ with $AB=7$ , $AD=4$ , $BC=3$ , $CD=2$ and no direct arcs $AC$ or $BD$ , complete Floyd's algorithm and write down the final distance matrix and final route matrix. Use them to state the shortest route from $A$ to $C$ and from $B$ to $D$ .
(8)
(Total for Question 1 is 8 marks)
2.
Explain why Dijkstra's algorithm can stop as soon as the destination vertex receives a final label, and explain why Floyd's algorithm must always complete all $n$ iterations.
(6)
(Total for Question 2 is 6 marks)
3.
For the network on $A$ to $G$ with arcs $AB=6$ , $AC=9$ , $AD=11$ , $BC=4$ , $BE=12$ , $CD=5$ , $CE=8$ , $CF=14$ , $DF=10$ , $EF=3$ , $EG=15$ , $FG=7$ , state the shortest route from $A$ to $G$ and its length, and determine the greatest amount by which the arc $EF$ could be lengthened before that route stops being shortest.
(8)
(Total for Question 3 is 8 marks)
4.
In a Dijkstra run on a network with vertices $A$ to $E$ , vertex $C$ has final label $12$ and vertex $E$ has final label $19$ , and the arc $CE$ has weight $7$ . State what this tells you about the shortest route to $E$ , and explain why the equality alone does not prove that $C$ lies on every shortest route to $E$ .
(5)
(Total for Question 4 is 5 marks)
5.
In the network on $A$ to $F$ with arcs $AB=5$ , $AC=8$ , $BC=2$ , $BD=9$ , $CD=4$ , $CE=7$ , $DF=6$ , $EF=4$ , the vertex $C$ must be avoided because of roadworks. Find the new shortest route from $A$ to $F$ and its length, and state by how much the closure increases the journey.
(7)
(Total for Question 5 is 7 marks)

Answer key

Answers begin on a new printed page so the question pack can be completed without the solutions alongside it.

D1-2.1 · The minimum spanning tree (minimum connector) problem. Prim's and Kruskal's algorithm.

Tier 1 · Easy

Mark scheme for D1-2.1 Tier 1 · Easy
Question	Scheme	Marks
1	Ascending order: $BC=3$ , $AC=4$ , $CD=5$ , $AB=6$ , $DE=7$ , $CE=8$ , $BD=9$ Accept $BC$ , accept $AC$ , accept $CD$ Reject $AB$ , since it forms the cycle $ABC$ Accept $DE$ ; the tree now has $4$ arcs and the algorithm stops Total weight $=3+4+5+7=19$	5
(5 marks)		5
Notes
Sorting the arcs gives $BC, AC, CD, AB, DE, CE, BD$ . Adding $BC$ , $AC$ and $CD$ creates no cycle and connects $A$ , $B$ , $C$ , $D$ . The next arc $AB$ would close the cycle $ABC$ , so it is rejected. Then $DE$ brings in the last vertex $E$ , giving $5-1=4$ arcs, so the algorithm terminates with weight $3+4+5+7=19$ .
2	A spanning tree is a subgraph that contains every vertex of the network, is connected and contains no cycles A tree on $n$ vertices has $n-1$ arcs A spanning tree on $9$ vertices has $8$ arcs	3
(3 marks)		3
Notes
A tree is a connected graph with no cycles, and it is spanning when it includes every vertex of the original network. Building a tree by adding one arc at a time connects one new vertex per arc after the first vertex, so a tree on $n$ vertices always has exactly $n-1$ arcs; with $n=9$ that gives $8$ arcs.

Tier 2 · Standard

Mark scheme for D1-2.1 Tier 2 · Standard
Question	Scheme	Marks
1	Add $AC=5$ Add $CD=6$ Add $CB=7$ Add $BE=8$ Add $EF=4$ Order of vertices joined: $A$ , $C$ , $D$ , $B$ , $E$ , $F$ Total weight $=5+6+7+8+4=30$	6
(6 marks)		6
Notes
Starting from $A$ , the shortest arc out of $\{A\}$ is $AC=5$ . From $\{A, C\}$ the choices are $AB=9$ , $AD=12$ , $BC=7$ , $CD=6$ , $CE=11$ , $CF=13$ , and the shortest is $CD=6$ . From $\{A, C, D\}$ the shortest arc to a new vertex is $CB=7$ , since $DF=10$ is longer. From $\{A, B, C, D\}$ the shortest is $BE=8$ , as $CE=11$ , $CF=13$ and $DF=10$ are all longer. Finally $EF=4$ brings in $F$ . The five arcs total $30$ .
2	Ascending order: $EF=4$ , $AC=5$ , $CD=6$ , $BC=7$ , $BE=8$ , $AB=9$ , $DF=10$ , $CE=11$ , $AD=12$ , $CF=13$ Accept $EF$ , then $AC$ , then $CD$ , then $BC$ , then $BE$ Each of those five arcs joins two components that were previously separate, so none of them closes a cycle No arc is rejected: after $BE$ the tree has $6-1=5$ arcs and every vertex is connected, so the algorithm stops The arcs $AB$ , $DF$ , $CE$ , $AD$ and $CF$ are therefore never considered Total weight $=4+5+6+7+8=30$	6
(6 marks)		6
Notes
Sorting gives $EF, AC, CD, BC, BE, AB, DF, CE, AD, CF$ . Arc $EF$ starts a component $\{E, F\}$ ; $AC$ starts a second one, which $CD$ and then $BC$ extend to $\{A, B, C, D\}$ ; finally $BE$ joins those two components together. Every arc taken has its two endpoints in different components at the moment it is tested, so no cycle is ever formed and this network gives the algorithm nothing to reject. After $BE$ the tree has $6-1=5$ arcs spanning all six vertices, so Kruskal's algorithm terminates and $AB$ , $DF$ , $CE$ , $AD$ and $CF$ are never reached. The total weight is $4+5+6+7+8=30$ , matching Prim's answer as it must.
3	Ascending order begins $EF=7$ , $BC=8$ , $CD=9$ , $AC=10$ , $FG=11$ , $DF=12$ , $BE=13$ , $AB=14$ Accept $EF$ , $BC$ , $CD$ , $AC$ , $FG$ Accept $DF$ , joining the two components $\{A, B, C, D\}$ and $\{E, F, G\}$ The tree now has $6$ arcs and every vertex is included, so the algorithm stops Minimum spanning tree: $EF$ , $BC$ , $CD$ , $AC$ , $FG$ , $DF$ Total weight $=7+8+9+10+11+12=57$	6
(6 marks)		6
Notes
Taking arcs in ascending order, $EF=7$ starts one component and $BC=8$ another; $CD=9$ and $AC=10$ extend the second to $\{A, B, C, D\}$ ; $FG=11$ extends the first to $\{E, F, G\}$ . The next arc $DF=12$ is the first that joins the two components, and it is accepted. That gives $7-1=6$ arcs covering all seven vertices, so $BE$ , $AB$ , $CE$ , $AD$ , $EG$ and $CF$ are never required. The weight is $7+8+9+10+11+12=57$ .

Tier 3 · Hard

Mark scheme for D1-2.1 Tier 3 · Hard
Question	Scheme	Marks
1	Add $AC=10$ , joining $C$ Add $CB=8$ , joining $B$ Add $CD=9$ , joining $D$ Add $DF=12$ , joining $F$ Add $FE=7$ , joining $E$ Add $FG=11$ , joining $G$ Order of vertices: $A$ , $C$ , $B$ , $D$ , $F$ , $E$ , $G$ Total weight $=10+8+9+12+7+11=57$ , which agrees with Kruskal	7
(7 marks)		7
Notes
From $\{A\}$ the arcs available are $AB=14$ , $AC=10$ , $AD=17$ , so $AC$ is chosen. From $\{A, C\}$ the shortest arc to a new vertex is $CB=8$ . From $\{A, B, C\}$ the candidates are $AD=17$ , $CD=9$ , $BE=13$ , $CE=16$ , $CF=21$ , so $CD=9$ is chosen. From $\{A, B, C, D\}$ the candidates are $BE=13$ , $CE=16$ , $CF=21$ , $DF=12$ , so $DF=12$ is chosen. From $\{A, B, C, D, F\}$ the shortest is $FE=7$ , and finally $FG=11$ beats $EG=19$ . Both algorithms must return the same minimum weight, and $10+8+9+12+7+11=57$ confirms it.
2	Prim's algorithm always adds an arc with exactly one endpoint already in the tree The other endpoint is a vertex not yet in the tree, so the new arc cannot close a cycle Kruskal's algorithm takes arcs purely in weight order, so both endpoints may already be in the growing forest That is why every Kruskal arc must be tested for a cycle before it is accepted Kruskal is more convenient when the data arrives as a sorted list of arcs rather than as a full distance matrix or drawn network	5
(5 marks)		5
Notes
Prim's algorithm grows one connected tree and only ever considers arcs from a vertex inside the tree to a vertex outside it, so adding such an arc joins a new vertex and leaves a tree. Kruskal's algorithm builds a forest of several components at once, so an arc taken in weight order can have both endpoints in the same component; that arc must be rejected, which is exactly the cycle test. If a problem gives the arcs already listed with their weights, Kruskal needs only a sort and a connectivity check, while Prim would first have to reconstruct which arcs meet each vertex.
3	Add $DC=6$ , joining $C$ Add $CA=5$ , joining $A$ Add $CB=7$ , joining $B$ Add $BE=8$ , joining $E$ Add $EF=4$ , joining $F$ Order of vertices: $D$ , $C$ , $A$ , $B$ , $E$ , $F$ Total weight $=6+5+7+8+4=30$ The minimum spanning tree is a property of the network, not of the start vertex, so the minimum weight is the same wherever Prim begins	7
(7 marks)		7
Notes
From $\{D\}$ the arcs are $AD=12$ , $CD=6$ , $DF=10$ , so $DC$ is chosen. From $\{C, D\}$ the candidates are $AC=5$ , $AD=12$ , $BC=7$ , $CE=11$ , $CF=13$ , $DF=10$ , and $CA=5$ wins. From $\{A, C, D\}$ the shortest arc to a new vertex is $CB=7$ ; then $BE=8$ ; then $EF=4$ . The arcs selected are the same five as when Prim starts at $A$ , though in a different order, and the weight is $30$ . In general the start vertex changes the order of selection but not the set of minimum-weight trees, because the minimum connector is determined by the arc weights alone.
4	Removing the arc of weight $8$ splits the tree into two components New weight $=30-8+13=35$ Any spanning tree must contain at least one arc joining the two components The cheapest such arc has weight $13$ , so no spanning tree of the reduced network is lighter than $35$ An arc with both endpoints in the same component would leave the two parts disconnected Such an arc would create a cycle rather than reconnect the tree, so it cannot be used as the replacement	6
(6 marks)		6
Notes
Deleting an arc of a spanning tree always leaves exactly two components. Every spanning tree of the reduced network must include at least one arc across the cut between them, so its weight is at least $30-8$ plus the smallest crossing weight; taking the cheapest crossing arc, of weight $13$ , achieves that bound and gives $35$ . An arc whose endpoints lie in the same component adds a cycle to that component while leaving the other component unreachable, so it fails the spanning condition and cannot serve as the replacement.
5	The arcs $BC=3$ and $AC=4$ join $A$ , $B$ , $C$ at a cost of $7$ and are always chosen The tree must then reach $D$ and $E$ Using $CD$ , the cheapest completion is $CD$ then $DE$ , costing $k+7$ Avoiding $CD$ , the cheapest completion is $CE=8$ then $DE=7$ , costing $15$ Total weight $=7+\min(k+7,\;15)$ $CD$ is used when $k+7<15$ , that is $0<k<8$ , with a tie at $k=8$ For $k=10$ the minimum spanning tree is $BC$ , $AC$ , $CE$ , $DE$ of weight $3+4+8+7=22$	7
(7 marks)		7
Notes
The arcs $BC=3$ and $AC=4$ are the two cheapest and connect $A$ , $B$ and $C$ for $7$ . Two further arcs must bring in $D$ and $E$ . With $CD$ available the cheapest pair is $CD=k$ followed by $DE=7$ , costing $k+7$ ; the alternative $CD$ then $CE=8$ costs $k+8$ and is never better. Without $CD$ the cheapest pair is $CE=8$ followed by $DE=7$ , costing $15$ , which beats $BD=9$ with $DE=7$ at $16$ . The tree weight is therefore $7+\min(k+7, 15)$ , so $CD$ appears exactly while $k<8$ , with both trees weighing $22$ at $k=8$ . At $k=10$ the arc $CD$ is not used and the tree $BC$ , $AC$ , $CE$ , $DE$ has weight $22$ .

D1-2.2 · Dijkstra's and Floyd's algorithm for finding the shortest path.

Tier 1 · Easy

Mark scheme for D1-2.2 Tier 1 · Easy
Question	Scheme	Marks
1	$A$ : order $1$ , final label $0$ $B$ : order $2$ , final label $4$ $C$ : order $3$ , working values $7$ then $6$ , final label $6$ $D$ : order $4$ , working values $12$ then $9$ , final label $9$ $E$ : order $5$ , working values $15$ then $14$ , final label $14$ Shortest path $ABCDE$ of length $14$	6
(6 marks)		6
Notes
Label $A$ with $0$ . Its neighbours take working values $B=4$ and $C=7$ , so $B$ is labelled second with $4$ . From $B$ , $C$ improves to $4+2=6$ and $D$ takes $4+8=12$ , so $C$ is labelled third with $6$ . From $C$ , $D$ improves to $6+3=9$ and $E$ takes $6+9=15$ , so $D$ is labelled fourth with $9$ . From $D$ , $E$ improves to $9+5=14$ , so $E$ is labelled fifth with $14$ . Tracing back, $14-9=5=DE$ , $9-6=3=CD$ , $6-4=2=BC$ and $4-0=4=AB$ , giving the path $ABCDE$ .
2	The order of labelling, the final label, and the working values The final label is the shortest distance from the start vertex A vertex receives a new working value each time a shorter route to it is found from a newly labelled vertex, so several working values can accumulate before the smallest becomes final	3
(3 marks)		3
Notes
The box records, in order, when the vertex was made permanent, the shortest distance to it from the start, and every trial distance found on the way. Each time a vertex is given a final label, all of its unlabelled neighbours are offered the new final label plus the connecting arc; whenever that offer beats the values already written, it is added to the list. The last, smallest working value becomes the final label.

Tier 2 · Standard

Mark scheme for D1-2.2 Tier 2 · Standard
Question	Scheme	Marks
1	$A$ : order $1$ , final $0$ $B$ : order $2$ , final $5$ $C$ : order $3$ , working $8$ then $7$ , final $7$ $D$ : order $4$ , working $14$ then $11$ , final $11$ $E$ : order $5$ , working $14$ , final $14$ $F$ : order $6$ , working $17$ , final $17$ Shortest route $ABCDF$ of length $17$	7
(7 marks)		7
Notes
Labelling $A$ with $0$ offers $B=5$ and $C=8$ , so $B$ is made final at $5$ . From $B$ , $C$ improves to $5+2=7$ and $D$ takes $5+9=14$ ; $C$ becomes final at $7$ . From $C$ , $D$ improves to $7+4=11$ and $E$ takes $7+7=14$ ; $D$ becomes final at $11$ . From $D$ , $F$ takes $11+6=17$ , and $E$ at $14$ is smaller, so $E$ becomes final at $14$ . From $E$ , $F$ would be $14+4=18$ , which does not beat $17$ , so $F$ is final at $17$ . Tracing back, $17-11=6=DF$ , $11-7=4=CD$ , $7-5=2=BC$ and $5-0=5=AB$ , giving $ABCDF$ .
2	$E$ : working values $18$ then $17$ , final label $17$ $F$ : working values $23$ , then $21$ , then $20$ , final label $20$ $G$ : working values $32$ then $27$ , final label $27$ The order of labelling is $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , $G$	7
(7 marks)		7
Notes
The first four final labels are $A=0$ , $B=6$ , $C=9$ and $D=11$ . From $B$ , $E$ takes $6+12=18$ ; from $C$ , $E$ improves to $9+8=17$ and $F$ takes $9+14=23$ ; from $D$ , $F$ improves to $11+10=21$ . The smallest working value is now $E=17$ , which becomes final; from $E$ , $F$ improves to $17+3=20$ and $G$ takes $17+15=32$ . Then $F=20$ becomes final and offers $G$ the value $20+7=27$ , which beats $32$ , so $G$ is final at $27$ .
3	Initial distances, with rows and columns in the order $A$ , $B$ , $C$ , $D$ : row $A$ is $0, 7, -, 4$ ; row $B$ is $7, 0, 3, -$ ; row $C$ is $-, 3, 0, 2$ ; row $D$ is $4, -, 2, 0$ , where a dash means no direct arc Initial route matrix: every entry in column $A$ is $A$ , in column $B$ is $B$ , in column $C$ is $C$ and in column $D$ is $D$ Iteration $1$ uses $k=A$ $d_{BD}$ becomes $d_{BA}+d_{AD}=7+4=11$ , and $r_{BD}$ becomes $r_{BA}=A$ $d_{DB}$ becomes $d_{DA}+d_{AB}=4+7=11$ , and $r_{DB}$ becomes $r_{DA}=A$ No other entry improves on iteration $1$	6
(6 marks)		6
Notes
The distance matrix records the direct arc weights with zeros on the diagonal and a dash where no arc exists; the route matrix starts with column $j$ filled entirely with the label $j$ . Iteration $1$ tests every $d_{ij}$ against $d_{iA}+d_{Aj}$ . The only entries that are currently missing and can be filled through $A$ are $BD$ and $DB$ , each becoming $7+4=11$ , and their route entries are set to $r_{BA}=A$ and $r_{DA}=A$ respectively. Entries such as $d_{BC}=3$ are already shorter than any route through $A$ , so they are unchanged.

Tier 3 · Hard

Mark scheme for D1-2.2 Tier 3 · Hard
Question	Scheme	Marks
1	Final distances, rows and columns in the order $A$ , $B$ , $C$ , $D$ : row $A$ is $0, 7, 6, 4$ ; row $B$ is $7, 0, 3, 5$ ; row $C$ is $6, 3, 0, 2$ ; row $D$ is $4, 5, 2, 0$ Final routes: row $A$ is $A, B, D, D$ ; row $B$ is $A, B, C, C$ ; row $C$ is $D, B, C, D$ ; row $D$ is $A, C, C, D$ Shortest route from $A$ to $C$ : $r_{AC}=D$ , then $r_{DC}=C$ , giving $ADC$ of length $6$ Shortest route from $B$ to $D$ : $r_{BD}=C$ , then $r_{CD}=D$ , giving $BCD$ of length $5$	8
(8 marks)		8
Notes
Iteration $k=A$ fills $d_{BD}=d_{DB}=11$ with route entry $A$ . Iteration $k=B$ gives $d_{AC}=d_{AB}+d_{BC}=7+3=10$ with $r_{AC}=r_{AB}=B$ , and symmetrically $d_{CA}=10$ with $r_{CA}=B$ . Iteration $k=C$ gives $d_{BD}=d_{BC}+d_{CD}=3+2=5$ , improving on $11$ , with $r_{BD}=r_{BC}=C$ , and symmetrically $d_{DB}=5$ with $r_{DB}=C$ . Iteration $k=D$ gives $d_{AC}=d_{AD}+d_{DC}=4+2=6$ , improving on $10$ , with $r_{AC}=r_{AD}=D$ , and symmetrically $d_{CA}=6$ with $r_{CA}=D$ . Reading the route matrix, $A$ to $C$ goes first to $D$ and then $D$ to $C$ goes direct, so the route is $ADC$ ; $B$ to $D$ goes first to $C$ and then direct, giving $BCD$ .
2	Dijkstra makes final the vertex with the smallest working value at each stage All arc weights are non-negative, so no route discovered later can be shorter than a label already made final Once the destination is made final its label cannot improve, so the algorithm may stop Floyd improves entries only by routing through the vertex $k$ of the current iteration A shortest route may pass through a vertex whose iteration has not yet been run Omitting iteration $k$ would leave every improvement that uses $k$ undiscovered, so all $n$ iterations are needed	6
(6 marks)		6
Notes
Dijkstra's correctness rests on non-negative weights: the smallest outstanding working value cannot be beaten by extending any longer route, so making it final is safe and the destination's label is already optimal when it is made final. Floyd's algorithm, by contrast, considers intermediate vertices one at a time, and after iteration $k$ the matrix holds the shortest routes that use only $A$ to $k$ as intermediates. A route that passes through a later vertex is simply not yet representable, so the algorithm has no valid stopping point before the final iteration.
3	Shortest route $ACEFG$ of length $27$ Check: $9+8+3+7=27$ The best route to $G$ avoiding $EF$ goes $A$ , $D$ , $F$ , $G$ Its length is $11+10+7=28$ The route $ACEFG$ has length $24+x$ when $EF=x$ It remains shortest while $24+x\leqslant28$ , that is $x\leqslant4$ $EF$ may be lengthened by at most $4-3=1$	8
(8 marks)		8
Notes
Dijkstra from $A$ gives final labels $A=0$ , $B=6$ , $C=9$ , $D=11$ , $E=17$ , $F=20$ , $G=27$ , and tracing back through $27-20=7=FG$ , $20-17=3=EF$ , $17-9=8=CE$ and $9-0=9=AC$ gives $ACEFG$ . If $EF$ is changed to $x$ the length of that route becomes $9+8+x+7=24+x$ . Every route to $G$ finishes with $FG=7$ or $EG=15$ . The best route reaching $F$ without using $EF$ is $ADF$ , of length $11+10=21$ , which beats $ACDF$ at $9+5+10=24$ , so the best rival through $F$ is $28$ ; the best route using $EG$ is $ACE$ then $EG$ , of length $17+15=32$ . The binding rival is therefore $28$ , and $ACEFG$ stays shortest while $24+x\leqslant28$ , that is $x\leqslant4$ , an increase of at most $1$ .
4	The difference of the final labels is $19-12=7$ , which equals the weight of $CE$ So there is a shortest route to $E$ whose last arc is $CE$ The route to $E$ is a shortest route to $C$ followed by the arc $CE$ Another vertex $X$ could satisfy the same equality, with final label of $E$ minus final label of $X$ equal to the weight of $XE$ In that case there are two shortest routes to $E$ of equal length, so $C$ need not lie on every one	5
(5 marks)		5
Notes
The trace-back rule is that an arc $XY$ lies on a shortest route to $Y$ exactly when the final label of $Y$ minus the final label of $X$ equals the weight of $XY$ ; here $19-12=7$ confirms that $CE$ is such an arc, so appending $CE$ to any shortest route to $C$ gives a shortest route to $E$ . The rule identifies one valid predecessor, not a unique one: if some other vertex also satisfies the equality, the network has two distinct shortest routes to $E$ of the same total length, and the trace-back would legitimately produce either.
5	With $C$ available the shortest route is $ABCDF$ of length $17$ Deleting $C$ removes the arcs $AC$ , $BC$ , $CD$ and $CE$ The only remaining arcs are $AB=5$ , $BD=9$ , $DF=6$ and $EF=4$ $E$ is now reachable only through $F$ , so no route to $F$ can use $E$ The only route from $A$ to $F$ is $ABDF$ Its length is $5+9+6=20$ The closure adds $20-17=3$ to the journey	7
(7 marks)		7
Notes
Removing $C$ also removes every arc incident to it, leaving only $AB$ , $BD$ , $DF$ and $EF$ . From $A$ the sole first step is $AB=5$ ; from $B$ the sole onward step is $BD=9$ ; from $D$ the sole onward step is $DF=6$ . The vertex $E$ now hangs off $F$ alone, so it cannot appear on a route into $F$ . The unique route is therefore $ABDF$ of length $20$ , which is $3$ more than the original shortest route $ABCDF$ of length $17$ .