D1.2.2 Dijkstra’s and Floyd’s algorithm for finding the shortest path.

Section
D1.2 Algorithms on graphs
Level
Partly A level only
Statement
Dijkstra’s and Floyd’s algorithm for finding the shortest path.
Guidance
When applying Floyd’s algorithm, unless directed otherwise, students will be expected to complete the first iteration on the first row of the corresponding distance and route problems, the second iteration on the second row and so on until the algorithm is complete.
Since 2018
38 parts, 151 marks · topic pages: Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd), Route inspection and the travelling salesman problem, Algorithms, sorting, bin packing and graph theory, Dynamic programming

Back to the checklist

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)
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)
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)
June 2025 · Paper 3D (Decision 1) · Q3(c) 3 marks
The final time matrix after completion of Floyd’s algorithm is shown below. A B C E F G A – B – C – – E – F – G – Albert must visit each village. He will start and finish at B and wishes to minimise the total time taken to visit each village. (c) (i) Use the nearest neighbour algorithm, starting at B, to find a Hamiltonian cycle in the complete network of shortest times shown above. (ii) Find the total travel time for this cycle. (iii) Given that he travels the Hamiltonian cycle found in (c)(i), interpret this cycle in terms of the actual villages visited by Albert. (3)
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)
June 2025 · Paper 3D (Decision 1) · Q4(b) 5 marks
On Monday afternoon, Turvi needs a route that traverses each corridor at least once. She plans to start at J and finish at A and wants to minimise the distance travelled. (b) (i) By considering the pairings of all relevant nodes, find the corridors that would need to be traversed twice. You must make your method and working clear. (ii) State the total length of this route. (5)
June 2025 · Paper 3D (Decision 1) · Q4(c) 2 marks
Turvi discovers that she cannot walk along corridors AB, CD and JK because they are being decorated. Turvi walks from J to A travelling along all the other corridors at least once. She does this in the minimum distance possible. (c) Determine the difference between the length of the route Turvi travels and the length of the route found in (b). You must make the values used in your calculation clear. (2)
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)
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)
June 2024 · Paper 3D (Decision 1) · Q3(b) 6 marks
Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track. (b) By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must • state which tracks she will repeat in her route • state the total length of her route (6)
June 2024 · Paper 3D (Decision 1) · Q3(c) 2 marks
The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route. (c) Determine which route, Abi’s or Tarig’s, is shorter. You must make your working clear. (2)
June 2023 · AS Paper 2 (Decision 1) · Q3(a) 1 mark
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)
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)
June 2023 · Paper 3D (Decision 1) · Q1(e) 1 mark
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)
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)
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)
June 2023 · Paper 3D (Decision 1) · Q3(b) 2 marks
2 , where n is the number of nodes in One application of Dijkstra’s algorithm has order n the network. It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes. (b) Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes. (2)
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)
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)
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)
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)
June 2022 · Paper 3D (Decision 1) · Q3(c) 4 marks
The final distance matrix after completion of Floyd’s algorithm is shown in Table 3. A B C E F A – B – C – – E – F – Table 3 Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled. (c) (i) Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances. (ii) Find the length of each of the two cycles. (iii) State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka’s route. (4)
Nov 2021 · Paper 3D (Decision 1) · Q4(a) 1 mark
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)
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)
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)
Nov 2021 · Paper 3D (Decision 1) · Q6(b) 3 marks
One application of Dijkstra’s algorithm has order n2 , where n is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra’s algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes. (b) Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer. (3)
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)
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)
Oct 2020 · Paper 3D (Decision 1) · Q3(c) 3 marks
The final time matrix after completion of Floyd’s algorithm is shown below. Final time matrix A B C E A – B – C – – E – (c) (i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times. (ii) Find the time taken for this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (3)
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)
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)
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)
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)
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)
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)
June 2019 · Paper 3D (Decision 1) · Q3(d) 4 marks
Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table. (d) (i) State the cycle obtained using the nearest neighbour algorithm. (ii) State the length of this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (iv) Prove that Mabintou’s cycle is not optimal. (4)
June 2019 · Paper 4D (Decision 2) · Q3(a) 1 mark
3. A –24 G E H B T S x –24 –17 –25 F I C –30 J Figure 1 In Figure 1 the weight of arc SB is denoted by x where x . 0 (a) Explain why Dijkstra’s algorithm cannot be used on the directed network in Figure 1. (1)
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)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.