Robinson Tuition
A-level Decision Mathematics 1 · Edexcel 9FM0 · free Further Maths worksheet

Floyd's algorithm

Distance and route tables, every iteration of Floyd's algorithm, reading a route.

12 original questions, 78 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

The network below shows the roads between four farms, A, B, C and D. The number on each arc is the length of the road in km. The road from D to C is one-way, as shown by the arrow.

Floyd's algorithm is to be used to find the shortest distances between every pair of farms.

  1. Complete the initial distance table and the initial route table.
  2. Explain why the first iteration of Floyd's algorithm makes no changes to either table.
692114ABCDInitial tablesDistance tableRoute tableABCDABCDABCDABCDDiagram NOT accurately drawn
4 marks
Show answer
a) Distance rows: A - 6 9 ∞; B 6 - 2 11; C 9 2 - ∞; D ∞ 11 4 -. Route table: every entry in column X is X b) Iteration 1 goes via A; the only routes through A are B-A-C (15 > 2) and C-A-B (15 > 2), and D cannot reach A directly, so nothing is shorter
2

The initial distance table and initial route table for a directed network with vertices A, B, C and D are shown below.

Perform the first iteration of Floyd's algorithm. You should show the distance table and the route table after this iteration.

Initial tablesDistance tableRoute tableABCDABCD-5∞35-4∞2∞-83∞8-ABCDABCDABCDABCDABCDABCDAfter the first iterationDistance tableRoute tableABCDABCDABCDABCD
3 marks
Show answer
BD becomes 8, CB becomes 7, CD becomes 5, DB becomes 8, each with route entry A
3

Floyd's algorithm has been applied to a network of roads between five towns, A, B, C, D and E. Some of the roads are one-way. The final distance table, in miles, and the final route table are shown below.

  1. Use the final route table to find the shortest route from A to E, explaining how you use the table. State the length of this route.
  2. Find the shortest route from E to D and its length.
Final tablesDistance tableRoute tableABCDEABCDE-8115158-397113-64596-1077410-ABCDEABCDEABBDCABCCCBBCDEACCDCACCCE
4 marks
Show answer
a) ABCE, 15 miles b) ECD, 10 miles
4

The network below shows the paths between four huts, A, B, C and D, on a nature reserve. The number on each arc is the walking time in minutes. The paths from B to D and from D to A are one-way, as shown by the arrows.

The initial distance and route tables are shown below the network.

  1. Use Floyd's algorithm to find the shortest walking times between every pair of huts. You should show the distance table and the route table after each iteration.
  2. Use your final route table to find the quickest route from D to B, and state its time.
732694ABCDInitial tablesDistance tableRoute tableABCDABCD-73∞7-2632-94∞9-ABCDABCDABCDABCDABCDABCDFirst iterationDistance tableRoute tableABCDABCDABCDABCDSecond iterationDistance tableRoute tableABCDABCDABCDABCDThird iterationDistance tableRoute tableABCDABCDABCDABCDFourth iterationDistance tableRoute tableABCDABCDABCDABCDDiagram NOT accurately drawn
9 marks
Show answer
a) Final distance table: A - 5 3 11; B 5 - 2 6; C 3 2 - 8; D 4 9 7 -. Final route table: A A C C C; B C B C D; C A B C B; D A C A D b) DACB, 9 minutes
5

Floyd's algorithm is being used to find the shortest times, in minutes, between five stations, A, B, C, D and E, on a tram network in which some links run in one direction only. The distance table and route table after the second iteration are shown below.

  1. Perform the third, fourth and fifth iterations of Floyd's algorithm. You should show the distance table and the route table after each iteration.
  2. Use your final tables to find the quickest journey from C to D and its time.
After the second iterationDistance tableRoute tableABCDEABCDE-4711144-37181014-2159710-2141852-ABCDEABCDEABBBEABCDAAACBEABBDEAACDEThird iterationDistance tableRoute tableABCDEABCDEABCDEABCDEFourth iterationDistance tableRoute tableABCDEABCDEABCDEABCDEFifth iterationDistance tableRoute tableABCDEABCDEABCDEABCDE
7 marks
Show answer
a) Iteration 3 (C): AE = 12, BE = 8 (route C). Iteration 4 (D): EA = 11, EB = 9 (route D). Iteration 5 (E): CD = 7, DC = 7 (route E) b) CED, 7 minutes
6

The initial distance table below gives the lengths, in metres, of the walkways between five buildings, A, B, C, D and E, on a hospital site. Some walkways are one-way.

ABCDE
A−126∞∞
B∞−5∞8
C65−94
D7∞9−3
E∞∞43−

The drawing of the network below is incomplete.

  1. By adding the arcs that join vertex A to the other vertices, with their weights and any arrows needed, complete the drawing of the network.
  2. Perform the first two iterations of Floyd's algorithm, starting from the initial tables given below the network. You should show the distance table and the route table after each iteration.
58943ABCDEInitial tablesDistance tableRoute tableABCDEABCDE-126∞∞∞-5∞865-947∞9-3∞∞43-ABCDEABCDEABCDEABCDEABCDEABCDEABCDEFirst iterationDistance tableRoute tableABCDEABCDEABCDEABCDESecond iterationDistance tableRoute tableABCDEABCDEABCDEABCDEDiagram NOT accurately drawn
6 marks
Show answer
a) AB with weight 12 and an arrow from A to B; AC with weight 6, no arrow; DA with weight 7 and an arrow from D to A b) Iteration 1: DB becomes 19, route A. Iteration 2: AE becomes 20, route B
7
  1. Explain the difference between the information given by Dijkstra's algorithm and the information given by Floyd's algorithm.
  2. Explain why, in the kth iteration of Floyd's algorithm, the entries in the kth row and the kth column of the distance table never change.
  3. Floyd's algorithm has cubic order. A computer takes 2.4 seconds to apply Floyd's algorithm to a network with 40 vertices. Estimate the time it would take to apply the algorithm to a network with 100 vertices.
5 marks
Show answer
a) Dijkstra finds the shortest distance (and route) from one vertex to every other vertex; Floyd finds the shortest distance (and route) between every pair of vertices b) For an entry in row k the new value would be d(k,k) + d(k,j) = 0 + d(k,j), which equals the current entry and is not smaller; similarly for column k c) 37.5 seconds
8

The network below shows the cycle routes between five villages, A, B, C, D and E. The number on each arc is the length of the route in km. The routes from A to D, from B to E and from E to D are one-way, as shown by the arrows.

  1. Complete the initial distance table and the initial route table.
  2. Perform the first two iterations of Floyd's algorithm. You should show the distance table and the route table after each iteration.
94143107132ABCDEInitial tablesDistance tableRoute tableABCDEABCDEABCDEABCDEFirst iterationDistance tableRoute tableABCDEABCDEABCDEABCDESecond iterationDistance tableRoute tableABCDEABCDEABCDEABCDEDiagram NOT accurately drawn
6 marks
Show answer
a) Distance rows: A - 9 4 14 ∞; B 9 - ∞ 3 10; C 4 ∞ - 7 13; D ∞ 3 7 - ∞; E ∞ ∞ 13 2 -. Route table: every entry in column X is X b) Iteration 1 (A): BC = 13, CB = 13. Iteration 2 (B): AD = 12, AE = 19, DA = 12, DE = 13
9

The network below shows the times, in minutes, to drive along the roads between five depots, A, B, C, D and E. The roads from B to D and from C to E are one-way. Floyd's algorithm has been applied to the network, with the vertices taken in the order A, B, C, D, E. The final distance table and a partially completed final route table are shown below.

  1. Complete the final route table, explaining how you found each missing entry.
  2. Use the final route table to find the quickest route from E to C and its time.
61194358ABCDEFinal tablesDistance tableRoute tableABCDEABCDE-61310116-749159-3816123-5111785-ABCDEABCDEABBEABDDDBCDECCDEADDEDiagram NOT accurately drawn
6 marks
Show answer
a) Row A column C: D; row C column A: B; row D column A: E; row E column B: A b) EDC, 8 minutes
10

A council runs a gritting service for six villages, A, B, C, D, E and F. Some of the roads between the villages are one-way. Floyd's algorithm has been used to find the shortest driving times, in minutes, between the villages. The final distance table and final route table are shown below.

The council will keep its gritting lorry at one of the villages. Each call-out is a return journey from that village to one other village and back again.

  1. Explain why the time from A to C is not the same as the time from C to A.
  2. Find the village at which the lorry should be kept so that the longest return journey is as short as possible. You must show your working.
  3. For the village chosen in (b), find the route of its longest return journey.
Final tablesDistance tableRoute tableABCDEFABCDEF-14917202014-7151824217-8111729158-693021146-102012191610-ABCDEFABCDEFABCCCFABCCCDBBCDEDCCCDEFFDDDEFABBEEF
8 marks
Show answer
a) Some roads are one-way (e.g. A to C is a direct one-way road), so the quickest route from C back to A must use different roads: 21 minutes against 9 b) C, longest return journey 36 minutes c) C to F is CDF, F to C is FBC: CDFBC, 36 minutes
11

Floyd's algorithm has been applied to a network of roads between six towns, A, B, C, D, E and F. Some of the roads are one-way. The final table of shortest times, in minutes, and the final route table are shown below.

Leila is a courier based in town A. She must deliver parcels to D and to E, in either order, and then return to A.

  1. Find the order in which Leila should make her deliveries so that her total time is as short as possible. State the total time.
  2. Use the final route table to write down the complete route Leila should take, listing every town she passes through.
  3. Explain why her route passes through town F twice.
Final tablesDistance tableRoute tableABCDEFABCDEF-12715221112-69172276-101518171610-8131621158-5112014412-ABCDEFABCDEFABCFCFABCDDEABCDEACCCDEEFCCDEFADDDDF
8 marks
Show answer
a) D first then E: 39 minutes (the other order takes 47) b) A F D E F A c) The quickest route from A to D goes via F and the quickest route from E back to A also goes via F; the tables give the best route for each stage separately
12

The network below shows the footpaths between five viewpoints, A, B, C, D and E, in a country park. The number on each arc is the walking time in minutes. The paths from A to C, from C to D and from E to A are one-way, as shown by the arrows.

  1. Complete the initial distance table and the initial route table.
  2. Perform the first three iterations of Floyd's algorithm. You should show the distance table and the route table after each iteration.

The final tables, after all five iterations, are shown below the tables for the iterations.

  1. Use the final route table to find the quickest route from A to E and from E to B. State the time of each.
  2. A new two-way path is to be built directly between B and E. Find the range of walking times for this path that would reduce the quickest time from B to E.
10631251448ABCDEInitial tablesDistance tableRoute tableABCDEABCDEABCDEABCDEFirst iterationDistance tableRoute tableABCDEABCDEABCDEABCDESecond iterationDistance tableRoute tableABCDEABCDEABCDEABCDEThird iterationDistance tableRoute tableABCDEABCDEABCDEABCDEFinal tablesDistance tableRoute tableABCDEABCDE-96111510-3812133-59121215-4816144-ABCDEABCDEACCCDABCCDBBCDDEBBDEADCDEDiagram NOT accurately drawn
12 marks
Show answer
a) Distance rows: A - 10 6 ∞ ∞; B 10 - 3 12 ∞; C ∞ 3 - 5 14; D ∞ 12 ∞ - 4; E 8 ∞ 14 4 -. Route table: every entry in column X is X b) Iteration 1 (A): EB = 18. Iteration 2 (B): AD = 22, CA = 13, DA = 22, DC = 15. Iteration 3 (C): AB = 9, AD = 11, AE = 20, BD = 8, BE = 17, EB = 17 c) A to E: ACDE, 15 minutes; E to B: EDB, 16 minutes d) Walking time less than 12 minutes

Your score

Answer the questions above and your score appears here.

Every question here is original and written by Robinson Tuition. It follows the Edexcel A-level Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.

All A-level Decision Mathematics 1 topics