Floyd's algorithm

Floyd's algorithm Test

Spec 2.2 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Floyd's algorithm

Total 27 marks

Name

Class

Date

  1. 1
    A network has four vertices AA, BB, CC and DD. The roads and their lengths are AB=2AB=2, AC=3AC=3, BC=7BC=7, BD=10BD=10 and CD=4CD=4. Floyd's algorithm is applied, with the pivots in the order AA, BB, CC, DD. In the distance table the leading diagonal is 0 and a dash means there is no direct road. In the route table, the entry in row XX, column YY is the first vertex to travel to when going from XX to YY; initially it is YY itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).
    (a)
    After iteration 1 (pivot AA), what is the entry in row BB, column CC of the distance table?
    [1 mark]
    • A77
    • B55
    • C33
    • D22
    (b)
    After iteration 1, what is the entry in row BB, column CC of the route table?
    [1 mark]
    • AAA
    • BCC
    • CBB
    • DDD
    (c)
    Complete the algorithm. Find the shortest distance from BB to DD and use the final route table to give the route.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    Five sites AA to EE are joined by roads with lengths in km: AB=5AB=5, BC=3BC=3, CD=6CD=6, DE=2DE=2, EA=12EA=12 and BE=11BE=11. Floyd's algorithm is applied, with the pivots in the order AA, BB, CC, DD, EE. In the route table, the entry in row XX, column YY is the first vertex to travel to when going from XX to YY; initially it is YY itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).
    (a)
    After iteration 2 (pivot BB), what is the entry in row AA, column CC of the distance table?
    [1 mark]
    • ANo entry (dash)
    • B33
    • C55
    • D88
    (b)
    After iteration 3 (pivot CC), what is the entry in row DD, column BB of the route table?
    [1 mark]
    • ABB
    • BAA
    • CCC
    • DEE
    (c)
    Complete the algorithm. Find the shortest distance from EE to CC and give the route.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    Four villages PP, QQ, RR and SS are joined by roads with lengths in km: PQ=3PQ=3, PR=5PR=5, QR=9QR=9, QS=7QS=7 and RS=2RS=2. Floyd's algorithm is applied, with the pivots in the order PP, QQ, RR, SS. In the route table, the entry in row XX, column YY is the first vertex to travel to when going from XX to YY; initially it is YY itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).
    (a)
    Carry out iterations 1 and 2. State each entry of the distance table that changes, with its new value, and the new route table entries.
    [3 marks]
    (b)
    Complete the algorithm. Find the shortest distance and route from PP to SS, and show that the shortest route from QQ to RR is not the direct road.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    A one-way system links four junctions AA, BB, CC and DD. The one-way roads and their lengths in km are A→B=4A\to B=4, A→C=9A\to C=9, B→C=3B\to C=3, B→D=12B\to D=12, C→D=5C\to D=5 and D→A=2D\to A=2. Floyd's algorithm is applied, with the pivots in the order AA, BB, CC, DD. A dash in the distance table means there is no route yet. In the route table, the entry in row XX, column YY is the first vertex to travel to when going from XX to YY; initially it is YY itself. Each iteration uses the next vertex in order as the pivot (iteration 1 uses the first row and column).
    (a)
    Carry out all four iterations of Floyd's algorithm. For each iteration, state the entries that change, with their new distance and route entry.
    [6 marks]
    (b)
    Use the final tables to find the shortest route from CC to BB and its length. Evaluate whether Floyd's algorithm is a better choice than Dijkstra's algorithm for a planner who needs the shortest distance between every pair of junctions.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests