How does Dijkstra's algorithm find the shortest path in a weighted graph?
Understand Dijkstra's shortest path algorithm, how it finds the lowest-cost path from a start vertex, the role of a priority queue, and its applications.
A focused answer to AQA A-Level Computer Science 4.3.4, covering Dijkstra's shortest path algorithm, how it finds the lowest-cost path from a start vertex in a weighted graph, the role of a priority queue, and its applications.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
AQA wants you to describe Dijkstra's shortest path algorithm, explain how it finds the lowest-cost path from a start vertex through a weighted graph, identify the role of a priority queue, and give applications, including tracing the algorithm on a small graph.
What Dijkstra's algorithm does
How it works
The key insight is that once the closest unvisited vertex is chosen, no later route can be shorter, because every remaining route would have to pass through a vertex that is already at least as far away. This is why a finalised vertex is never reconsidered, and it is also why negative weights break the algorithm. The predecessor records let you reconstruct the actual path by working back from the destination to the source.
Applications
Dijkstra's algorithm underpins satnav and mapping route-finding (weights are distance or travel time), network routing protocols that find least-cost paths for data packets, transport planning, and any problem of finding the cheapest or fastest route through a weighted network.
In each application the abstract graph maps onto something concrete: in a satnav the vertices are junctions and the edge weights are road lengths or expected travel times, so the lowest-cost path is the fastest route; in a network the vertices are routers and the weights are link costs, so the least-cost path is where packets should be forwarded. Because the weights can model anything additive and non-negative, the same algorithm solves a wide family of problems just by relabelling what a weight means.
It is worth contrasting Dijkstra with the unweighted breadth-first search, since the specification covers both. If every edge had weight 1, Dijkstra would visit vertices in exactly the same order as breadth-first search, because the closest vertex is always the one fewest edges away. Dijkstra generalises this to arbitrary non-negative weights by always finalising the cheapest-so-far vertex rather than the nearest in edge count. The reason negative weights break it is that finalising a vertex assumes no cheaper route can appear later, but a negative edge encountered afterwards could undercut a distance already treated as final, so the guarantee fails. For graphs with negative weights a different algorithm is needed, which is why the non-negative condition is always stated.
Exam-style practice questions
Practice questions written in the style of AQA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
AQA 20195 marksA weighted graph has vertices A, B, C and D. The edges and weights are A to B = 1, A to C = 4, B to C = 2, B to D = 5, C to D = 1. Use Dijkstra's algorithm from A to find the shortest distance to D, showing the tentative distances as they are updated.Show worked answer →
Initialise distances: A = 0, B = , C = , D = .
Visit A (distance 0): relax A to B = 1, A to C = 4. Distances: B = 1, C = 4, D = .
Visit B (smallest unvisited, distance 1): relax B to C gives , update C = 3; B to D gives , update D = 6.
Visit C (distance 3): relax C to D gives , update D = 4.
Visit D (distance 4): no further updates. Shortest distance A to D = 4, via A, B, C, D.
Markers reward correct initialisation, choosing the smallest unvisited vertex each step, each relaxation that updates a shorter distance, and the final answer of 4.
AQA 20223 marksExplain the role of the priority queue in Dijkstra's algorithm and state one real-world application of the algorithm.Show worked answer →
At each step Dijkstra's algorithm must select the unvisited vertex with the smallest tentative distance, because that vertex's shortest distance is now final and can be used to relax its neighbours. A priority queue stores the unvisited vertices ordered by tentative distance so that this minimum can be retrieved efficiently rather than searching the whole set each time, which improves performance on large graphs.
A real-world application is satnav or mapping route-finding, where road segments have weights such as distance or travel time and the algorithm finds the least-cost route. Network routing is another valid example.
Markers reward explaining that the queue lets the minimum-distance vertex be selected efficiently and a valid application.
Related dot points
- Understand graphs, vertices and edges, directed, undirected and weighted graphs, and how a graph is represented as an adjacency matrix or an adjacency list.
A focused answer to AQA A-Level Computer Science 4.2.4, covering graphs, vertices and edges, directed, undirected and weighted graphs, and the adjacency matrix and adjacency list representations with their trade-offs.
- Understand depth-first and breadth-first graph traversal, the data structures they use, and the pre-order, in-order and post-order tree traversal algorithms.
A focused answer to AQA A-Level Computer Science 4.3.1, covering depth-first and breadth-first graph traversal and the data structures they use, plus the pre-order, in-order and post-order tree traversal algorithms.
- Understand the linear search and binary search algorithms, how each works, their requirements, and their time complexity.
A focused answer to AQA A-Level Computer Science 4.3.2, covering the linear search and binary search algorithms, how each works, the requirement that binary search needs sorted data, and their time complexity.
- Understand the queue abstract data type, FIFO behaviour, linear, circular and priority queues, and the enqueue and dequeue operations using front and rear pointers.
A focused answer to AQA A-Level Computer Science 4.2.2, covering the queue abstract data type, FIFO behaviour, linear, circular and priority queues, and the enqueue and dequeue operations with front and rear pointers.
- Understand Big-O notation for time and space complexity, the common orders of growth, how to determine the complexity of an algorithm, and the meaning of best, average and worst case.
A focused answer to AQA A-Level Computer Science 4.3.5, covering Big-O notation for time and space complexity, the common orders of growth, determining the complexity of an algorithm, and best, average and worst case.
Sources & how we know this
- AQA A-level Computer Science (7517) specification — AQA (2015)