Lesson 3D.2.2

3D.2.2 Shortest paths: Dijkstra's and Floyd's algorithms Quiz: Pearson Edexcel Further Maths, Unit 36

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 3D.2.2, Shortest paths: Dijkstra's and Floyd's algorithms: 20 multiple choice questions for the Pearson Edexcel Further Maths (9FM0), Unit 36: Algorithms on graphs, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. What does Dijkstra's algorithm calculate in a network?

    • Single-source shortest paths
    • All-pairs shortest paths
    • Minimum spanning tree
    • Maximum flow

  2. Dijkstra's algorithm requires edge weights to be

    • non-negative
    • all equal
    • whole numbers only
    • negative

  3. What does Floyd's algorithm calculate in a network?

    • Eulerian trail
    • Minimum spanning tree
    • All-pairs shortest paths
    • Single-source shortest paths

  4. During iteration k of Floyd's algorithm, what is tested for every pair of vertices?

    • Removing vertex k
    • Doubling edge weights
    • Routing via vertex k
    • Reversing all edges

  5. What information does Dijkstra's algorithm assign to each vertex as a permanent label?

    • Distance and predecessor
    • Flow and capacity
    • Degree and colour
    • Weight and position

  6. What does the route matrix record during Floyd's algorithm?

    • Next vertex
    • Previous vertex
    • Total distance
    • Direct edges only

  7. Which classification best describes Dijkstra's algorithm?

    • Greedy algorithm
    • Backtracking
    • Divide and conquer
    • Dynamic programming

  8. A network has edges S-B 2, S-A 4, B-A 1, A-T 5 and B-T 8. What is the shortest distance from S to T?

    • 8
    • 10
    • 6
    • 9

  9. Edges S-A 3, S-B 5, A-B 1, A-D 6 and B-D 2 form a network. What is the shortest distance from S to D?

    • 8
    • 7
    • 6
    • 9

  10. Floyd's algorithm has d(2,1) = 4, d(1,3) = 5 and d(2,3) = infinity. What is d(2,3) after using vertex 1 as an intermediate?

    • 5
    • 4
    • 9
    • infinity

  11. Dijkstra's algorithm starts at S with edges S-B 2 and S-A 4. Which vertex is permanently labelled first after S?

    • S, with distance 2
    • A, with distance 4
    • T, with distance 9
    • B, with distance 2

  12. Why can Dijkstra's algorithm fail when a network contains negative edge weights?

    • Premature permanent labelling
    • Graph disconnection
    • Infinite loops
    • Excessive memory usage

  13. A network has A-B 3, B-C 4 and a direct edge A-C of length 10. After Floyd's algorithm, what is the shortest distance from A to C?

    • 3
    • 7
    • 10
    • 4

  14. Dijkstra's algorithm is run on a network with 6 vertices. How many vertices are permanently labelled in total?

    • 12
    • 5
    • 6
    • 36

  15. Edges S-A 2, A-T 2, S-B 1 and B-T 4 form a network. What is the shortest distance from S to T?

    • 5
    • 6
    • 4
    • 3

  16. Why does Dijkstra's algorithm not need to revisit permanently labelled vertices with non-negative weights?

    • Extending lengthens routes
    • Labels reset to zero
    • Vertices disconnect
    • Weights become negative

  17. A network has S-A 1, S-B 4, A-B 2, A-C 6, B-C 3 and C-T 1. What is the shortest distance from S to T?

    • 7
    • 9
    • 6
    • 8

  18. Roughly how many table updates does Floyd's algorithm make on a network with n vertices?

    • 2^n
    • n log n
    • n^3
    • n^2

  19. What feature in Floyd's algorithm indicates the presence of a negative cycle?

    • Infinite matrix value
    • Zero determinant
    • Negative diagonal entry
    • Negative row sum

  20. A network has S-A 3, S-B 7, A-B 2, A-C 4, B-C 1, C-T 3 and B-T 6. What is the shortest distance from S to T?

    • 9
    • 10
    • 13
    • 11

All Pearson Edexcel Further Maths quizzes