: Edexcel past-paper questions pack
Back to the topic page

Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd)

Past-paper questions pack

Name
Class
Date set
Date due
Score/ 150

Questions are numbered; the mark schemes (the answer key) follow on separate pages so the question pages can be handed out alone. www.alevelfurthermathstutor.com

Edexcel AS and A-level Further Maths past-paper questions since June 2018 · 43 parts, 150 marks · mark schemes follow the questions · www.alevelfurthermathstutor.com · Questions and mark schemes © Pearson Education Ltd

1. June 2025 · AS Paper 2 (Decision 1) · Q1(b) · 2 marks
B E A F C Figure 1 (b) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for the network in Figure 1. You must list the arcs in the order in which you select them. (2)
2. June 2025 · AS Paper 2 (Decision 1) · Q1(c) · 2 marks
(c) (i) Draw the minimum spanning tree on Diagram 1 in the answer book. (ii) Find the weight of the minimum spanning tree. (2)
3. June 2025 · AS Paper 2 (Decision 1) · Q3(b) · 6 marks
(b) (i) Use Dijkstra’s algorithm to find the quickest path from A to J. (ii) State the shortest time needed to walk from A to J. (6)
4. June 2025 · Paper 3D (Decision 1) · Q3(a) · 2 marks
3. G F A E B C Figure 1 Direct roads between seven villages, A, B, C, D, E, F and G, are represented in Figure 1. The weight on each arc is the time, in minutes, taken to travel along the corresponding road. Three roads, AB, AD and GE, are one-way, as indicated by the arrow on the corresponding arc. Floyd’s algorithm is to be used to find the complete network of shortest times between the seven villages. (a) Set up an initial time matrix for this network. (2)
5. June 2025 · Paper 3D (Decision 1) · Q3(b) · 5 marks
The time matrix after three iterations of Floyd’s algorithm is shown below. A B C E F G A – B – ∞ ∞ C – ∞ ∞ – ∞ E – F – ∞ G – (b) Perform the next two iterations of Floyd’s algorithm that follow from the table above. You should show only the time matrix after each iteration. (5)
6. June 2025 · Paper 3D (Decision 1) · Q4(a) · 6 marks
4. B E J F C A K G H Figure 2 [The total weight of the network is 268] Figure 2 represents a network of corridors between 10 offices, A, B, C, D, E, F, G, H, J and K, in a building. The number on each edge represents the length, in metres, of the corresponding corridor. On Monday morning, Turvi needs to walk from J to K via A. She wishes to minimise the distance she travels along the corridors. (a) (i) Use Dijkstra’s algorithm, starting at A, to find the shortest route from J to K via A. (ii) State the length of this route. (6)
7. June 2024 · AS Paper 2 (Decision 1) · Q3(b) · 6 marks
Figure 3 represents a network of walkways in a warehouse. The arcs represent the walkways and the nodes represent junctions between them. The number on each arc represents the length, in metres, of the corresponding walkway. The values x and y are unknown, however it is known that x and y are integers and that 9 < x < y < 14 (b) (i) Use Dijkstra’s algorithm to find the shortest route from A to M. (ii) State an expression for the length of the shortest route from A to M. (6)
8. June 2024 · Paper 3D (Decision 1) · Q2(a) · 3 marks
2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J. A B C E F G H J A – B – C – – E – F – G – H – J – (a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree. (3)
9. June 2024 · Paper 3D (Decision 1) · Q2(b) · 1 marks
(b) State the weight of the minimum spanning tree found in part (a). (1)
10. June 2024 · Paper 3D (Decision 1) · Q2(c) · 1 marks
(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. (1)
11. June 2024 · Paper 3D (Decision 1) · Q3(a) · 5 marks
3. B E K A J F C G H Figure 1 [The total weight of the network is 413] Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track. (a) Use Dijkstra’s algorithm to find the shortest path from A to J. (5)
12. June 2023 · AS Paper 2 (Decision 1) · Q3(a) · 1 marks
3. C H G J B A E F Figure 2 Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel. Given that Dijkstra’s algorithm is to be applied only once to find Dyfan’s route, (a) explain why the algorithm should begin at C. (1)
13. June 2023 · AS Paper 2 (Decision 1) · Q3(b) · 6 marks
(b) Use Dijkstra’s algorithm to find the shortest route from A to J via C. State this route and its length. (6)
14. June 2023 · AS Paper 2 (Decision 1) · Q3(c) · 3 marks
(c) Use Prim’s algorithm, starting at C, to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree. (3)
15. June 2023 · AS Paper 2 (Decision 1) · Q3(d) · 1 marks
(d) State the total length, in km, of the minimum spanning tree. (1)
16. June 2023 · Paper 3D (Decision 1) · Q1(e) · 1 marks
E A B C Figure 2 Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages. (e) For the network represented in Figure 2, complete the initial time matrix in the answer book. (1)
17. June 2023 · Paper 3D (Decision 1) · Q1(f) · 2 marks
The time matrix after four iterations of Floyd’s algorithm is shown in Table 1. A B C E A – B – C – – E – Table 1 (f) Perform the final iteration of Floyd’s algorithm that follows from Table 1, showing the time matrix for this iteration. (2)
18. June 2023 · Paper 3D (Decision 1) · Q3(a) · 6 marks
3. B E J A G C F H Figure 4 Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J. The number on each edge gives the length of the corresponding edge. (a) (i) Use Dijkstra’s algorithm to find the shortest path from A to J. (ii) State the length of the shortest path from A to J. (6)
19. June 2023 · Paper 3D (Decision 1) · Q5(b) · 3 marks
(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3)
20. June 2022 · AS Paper 2 (Decision 1) · Q1(b) · 3 marks
C A F G E B Figure 1 (b) Use Kruskal’s algorithm to find the minimum spanning tree for the network in Figure 1. You should list the arcs in the order in which you consider them. For each arc, state whether or not you are adding it to your minimum spanning tree. (3)
21. June 2022 · AS Paper 2 (Decision 1) · Q1(c) · 2 marks
(c) (i) Draw the minimum spanning tree on Diagram 1 in the answer book. (ii) State the total weight of the tree. (2)
22. June 2022 · AS Paper 2 (Decision 1) · Q3(c) · 5 marks
Figure 2 represents a network of cycle tracks between eight villages, A, B, C, D, E, F, G and H. The number on each arc represents the length, in km, of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H. (c) Use Dijkstra’s algorithm to find the shortest path that Samira can take. (5)
23. June 2022 · Paper 3D (Decision 1) · Q2(a) · 6 marks
2. B H E A C J K F G Figure 1 [The total weight of the network is 299] Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track. One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels. (a) (i) Use Dijkstra’s algorithm to find the shortest path from A to K. (ii) State the length of the shortest path from A to K. (6)
24. June 2022 · Paper 3D (Decision 1) · Q3(a) · 2 marks
3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one‑way only. A B C E F A – B – ∞ ∞ C – ∞ ∞ – ∞ E ∞ ∞ – F ∞ ∞ – Table 1 (a) By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. (2)
25. June 2022 · Paper 3D (Decision 1) · Q3(b) · 4 marks
Floyd’s algorithm is to be used to find the complete network of shortest distances between the six classrooms. The distance matrix after two iterations of Floyd’s algorithm is shown in Table 2. A B C E F A – B – C – – E ∞ ∞ – F – Table 2 (b) Perform the next two iterations of Floyd’s algorithm that follow from Table 2. You should show the distance matrix after each iteration. (4)
26. Nov 2021 · Paper 3D (Decision 1) · Q3(a) · 3 marks
3. A B C E F G H A – B – C – – E – F – G – H – Table 1 Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H. (a) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree. (3)
27. Nov 2021 · Paper 3D (Decision 1) · Q3(b) · 1 marks
(b) State the weight of the minimum spanning tree. (1)
28. Nov 2021 · Paper 3D (Decision 1) · Q4(a) · 1 marks
4. A B C F E Figure 3 [The total weight of the network is 1648] Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd’s algorithm is to be used to find the complete network of shortest times between the six cities. An initial route matrix is given in the answer book. (a) Set up the initial time matrix. (1)
29. Nov 2021 · Paper 3D (Decision 1) · Q4(b) · 2 marks
(b) Perform the first iteration of Floyd’s algorithm. You should show the time and route matrices after this iteration. (2)
30. Nov 2021 · Paper 3D (Decision 1) · Q6(a) · 6 marks
6. B E F A G C H Figure 4 In Figure 4 the weights on the arcs represent distances. (a) (i) Use Dijkstra’s algorithm to find the shortest path from A to H. (ii) State the length of the shortest path from A to H. (6)
31. Oct 2020 · AS Paper 2 (Decision 1) · Q3(b) · 3 marks
Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road. Prim’s algorithm, starting at A, is applied to the network. The order in which the arcs are selected is AD, DH, DG, FG, EF, CG, BD. It is given that the order in which the arcs are selected is unique. (b) Using this information, find the smallest possible range of values for x, showing your working clearly. (3)
32. Oct 2020 · Paper 3D (Decision 1) · Q1(a) · 2 marks
1. The table below shows the lengths, in km, of the roads in a network connecting seven towns, A, B, C, D, E, F and G. A B C E F G A – – – – B – – – – C – – – – – E – – – F – – – G – – – – (a) By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book. (2)
33. Oct 2020 · Paper 3D (Decision 1) · Q1(b) · 3 marks
(b) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)
34. Oct 2020 · Paper 3D (Decision 1) · Q1(c) · 1 marks
(c) State the weight of the minimum spanning tree. (1)
35. Oct 2020 · Paper 3D (Decision 1) · Q3(a) · 2 marks
3. A B C E Figure 2 Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc. Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages. (a) Set up initial time and route matrices. (2)
36. Oct 2020 · Paper 3D (Decision 1) · Q3(b) · 4 marks
The matrices after two iterations of Floyd’s algorithm are shown below. Time matrix Route matrix A B C E A B C E A A – A B C B B – B A B C A E C – C A B C A E – A A C E E – E B B C E (b) Perform the next two iterations of Floyd’s algorithm that follow from the tables above. You should show the time and route matrices after each iteration. (4)
37. Oct 2020 · Paper 3D (Decision 1) · Q6(b) · 9 marks
The weights on the arcs in Figure 4 represent distances. The weight on arc EF is x where 12 < x < 26 and the weight on arc DG is y where 0 < y < 10 An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at A and has a length of 409 It is also given that the length of the shortest route from F to G via A is 140 (b) Using appropriate algorithms, find the value of x and the value of y. (9)
38. June 2019 · AS Paper 2 (Decision 1) · Q4(a) · 7 marks
4. B E x + y C F A H 3x + y G Figure 1 [The total weight of the network is 135 + 4x + 2y] The weights on the arcs in Figure 1 represent distances. The weights on the arcs CE and GH are given in terms of x and y, where x and y are positive constants and 7 : x + y : 20 There are three paths from A to H that have the same minimum length. (a) Use Dijkstra’s algorithm to find x and y. (7)
39. June 2019 · Paper 3D (Decision 1) · Q2(a) · 6 marks
2. B E C A J G F H Figure 1 [The total weight of the network is 370] Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor. (a) Use Dijkstra’s algorithm to find the shortest path from A to D, stating the path and its length. (6)
40. June 2019 · Paper 3D (Decision 1) · Q3(a) · 2 marks
3. B C A E Figure 2 The network in Figure 2 shows the direct roads linking five villages, A, B, C, D and E. The number on each arc represents the length, in miles, of the corresponding road. The roads from A to E and from C to B are one-way, as indicated by the arrows. (a) Complete the initial distance and route tables for the network provided in the answer book. (2)
41. June 2019 · Paper 3D (Decision 1) · Q3(b) · 5 marks
(b) Perform the first three iterations of Floyd’s algorithm. You should show the distance table and the route table after each of the three iterations. (5)
42. June 2019 · Paper 3D (Decision 1) · Q3(c) · 3 marks
After five iterations of Floyd’s algorithm the final distance table and partially completed final route table are shown below. Distance table Route table A B C E A B C E A – A A B – B A B C – C A B C – C C C E – E E (c) (i) Explain how the partially completed final route table can be used to find the shortest route from E to A. (ii) State this route. (3)
43. June 2018 · AS Paper 2 (Decision 1) · Q1(a) · 6 marks
1. B C A E A I G J H Figure 1 Figure 1 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. (a) (i) Use Dijkstra’s algorithm to find the shortest time needed to travel from A to H. (ii) State the quickest route. (6)

Mark schemes

Each mark scheme shows the whole question; the parts on this topic are the ones listed above.

June 2025 · AS Paper 2 (Decision 1) · Q1
Mark scheme June 2025 Paper 2 (Decision 1) Q1(c)
June 2025 · AS Paper 2 (Decision 1) · Q3
Mark scheme June 2025 Paper 2 (Decision 1) Q3(b)
June 2025 · Paper 3D (Decision 1) · Q3
Mark scheme June 2025 Paper 3D (Decision 1) Q3(b)
June 2025 · Paper 3D (Decision 1) · Q4
Mark scheme June 2025 Paper 3D (Decision 1) Q4(a)
June 2024 · AS Paper 2 (Decision 1) · Q3
Mark scheme June 2024 Paper 2 (Decision 1) Q3(b)
June 2024 · Paper 3D (Decision 1) · Q2
Mark scheme June 2024 Paper 3D (Decision 1) Q2(c)
June 2024 · Paper 3D (Decision 1) · Q3
Mark scheme June 2024 Paper 3D (Decision 1) Q3(a)
June 2023 · AS Paper 2 (Decision 1) · Q3
Mark scheme June 2023 Paper 2 (Decision 1) Q3(d)
June 2023 · Paper 3D (Decision 1) · Q1
Mark scheme June 2023 Paper 3D (Decision 1) Q1(f)
June 2023 · Paper 3D (Decision 1) · Q3
Mark scheme June 2023 Paper 3D (Decision 1) Q3(a)
June 2023 · Paper 3D (Decision 1) · Q5
Mark scheme June 2023 Paper 3D (Decision 1) Q5(b)
June 2022 · AS Paper 2 (Decision 1) · Q1
Mark scheme June 2022 Paper 2 (Decision 1) Q1(c)
June 2022 · AS Paper 2 (Decision 1) · Q3
Mark scheme June 2022 Paper 2 (Decision 1) Q3(c)
June 2022 · Paper 3D (Decision 1) · Q2
Mark scheme June 2022 Paper 3D (Decision 1) Q2(a)
June 2022 · Paper 3D (Decision 1) · Q3
Mark scheme June 2022 Paper 3D (Decision 1) Q3(b)
Nov 2021 · Paper 3D (Decision 1) · Q3
Mark scheme Nov 2021 Paper 3D (Decision 1) Q3(b)
Nov 2021 · Paper 3D (Decision 1) · Q4
Mark scheme Nov 2021 Paper 3D (Decision 1) Q4(b)
Nov 2021 · Paper 3D (Decision 1) · Q6
Mark scheme Nov 2021 Paper 3D (Decision 1) Q6(a)
Oct 2020 · AS Paper 2 (Decision 1) · Q3
Mark scheme Oct 2020 Paper 2 (Decision 1) Q3(b)
Oct 2020 · Paper 3D (Decision 1) · Q1
Mark scheme Oct 2020 Paper 3D (Decision 1) Q1(c)
Oct 2020 · Paper 3D (Decision 1) · Q3
Mark scheme Oct 2020 Paper 3D (Decision 1) Q3(b)
Oct 2020 · Paper 3D (Decision 1) · Q6
Mark scheme Oct 2020 Paper 3D (Decision 1) Q6(b)
June 2019 · AS Paper 2 (Decision 1) · Q4
Mark scheme June 2019 Paper 2 (Decision 1) Q4(a)
June 2019 · Paper 3D (Decision 1) · Q2
Mark scheme June 2019 Paper 3D (Decision 1) Q2(a)
June 2019 · Paper 3D (Decision 1) · Q3
Mark scheme June 2019 Paper 3D (Decision 1) Q3(c)
June 2018 · AS Paper 2 (Decision 1) · Q1
Mark scheme June 2018 Paper 2 (Decision 1) Q1(a)