Lesson 4.3.6.1

4.3.6.1 Dijkstra's shortest path algorithm Quiz: AQA Computer Science, Unit 3

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 4.3.6.1, Dijkstra's shortest path algorithm: 20 multiple choice questions for the AQA Computer Science (7517), Unit 3: Fundamentals of algorithms, 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 is Dijkstra's algorithm used for?

    • Searching sorted lists
    • Finding shortest paths in a weighted graph
    • Compressing data
    • Sorting numbers into ascending order by repeatedly swapping them

  2. Dijkstra's shortest path algorithm belongs to which category in the specification?

    • Sorting
    • Optimisation
    • Encryption
    • Parsing

  3. Dijkstra's algorithm requires edge weights to be which kind of values?

    • Non-negative
    • Integers only
    • Negative only
    • All equal to 1

  4. Which application is a typical use of shortest-path algorithms?

    • Hashing a password
    • Rendering a font
    • Compressing a video file
    • Route planning in a satellite navigation system

  5. At each step, which node does Dijkstra's algorithm select next?

    • The unvisited node with the smallest known distance from the source
    • The node with the highest label
    • The unvisited node with the largest distance, so the far nodes are reached first
    • The node with the most edges

  6. The specification says students will not be expected to recall the steps of Dijkstra's algorithm. What is expected instead?

    • Understanding the algorithm and being able to trace it
    • Coding it from memory in assembly language
    • Proving its correctness formally
    • Recalling the steps word for word

  7. Graph: S-A weight 4, S-B weight 1, B-A weight 2, A-T weight 3, B-T weight 6. What is the shortest distance from S to T?

    • 6
    • 4
    • 7
    • 10

  8. In the same graph (S-A 4, S-B 1, B-A 2, A-T 3, B-T 6), what is the shortest distance from S to A?

    • 3
    • 2
    • 6
    • 4

  9. In the same graph, which node is finalised first after the source S?

    • B, with tentative distance 1
    • All nodes simultaneously
    • A, with tentative distance 4
    • T, with tentative distance 6

  10. On a graph where every edge has weight 1, Dijkstra's algorithm gives the same result as which search?

    • Binary search
    • Breadth-first search
    • Bubble sort
    • Depth-first search

  11. Graph: S-A weight 2, A-T weight 2, S-T weight 5. What is the shortest distance from S to T?

    • 5
    • 2
    • 4
    • 7

  12. Why can negative edge weights break Dijkstra's algorithm?

    • A finalised node may later have a cheaper route via a negative edge, which is missed
    • The algorithm then runs in exponential time
    • The algorithm requires all weights to be equal
    • Negative numbers cannot be stored in memory, so the weights would overflow the data type

  13. Dijkstra's algorithm is an example of which kind of algorithm?

    • Greedy
    • Randomised
    • Brute force
    • Backtracking

  14. Graph: A-B weight 1, B-C weight 1, C-D weight 1, A-D weight 5. What is the shortest distance from A to D?

    • 7
    • 3
    • 5
    • 1

  15. During Dijkstra's algorithm the source has distance 0, and a neighbour X is joined to it by an edge of weight 7. What tentative distance does X receive?

    • Infinity
    • 0
    • 7
    • 14

  16. With a binary heap, what is the usual time complexity of Dijkstra's algorithm on V vertices and E edges?

    • O(V^2) only
    • O(n) always
    • O(2^V)
    • O((V + E) log V)

  17. Why do satellite navigation systems model roads as weighted graphs?

    • Weights are needed for Dijkstra's algorithm to terminate
    • Weighted graphs are always smaller
    • Roads have different lengths or travel times, so weights represent real costs
    • Unweighted graphs cannot store any roads at all, so weights are essential to the map

  18. Graph: S-A 1, S-B 4, A-B 2, B-T 1, A-T 6. What is the shortest distance from S to T?

    • 5
    • 6
    • 7
    • 4

  19. Which statement about Dijkstra's algorithm is correct?

    • It always finds the longest path
    • It finds shortest paths correctly in all graphs with negative weights
    • It only works on trees
    • It finds shortest paths from one source to all nodes when all weights are non-negative

  20. Why is breadth-first search not adequate when a two-edge path S-B-A costs 3 but the direct edge S-A costs 10?

    • It would choose the path with the most edges
    • It would choose the direct edge with fewer edges, giving a cost of 10 instead of 3
    • It would give a cost of 13
    • It cannot visit node A

All AQA Computer Science quizzes