Dijkstra's Shortest Path Algorithm

Breadth-first search finds the shortest path by edge count in an unweighted graph. When edges carry different weights — distances, costs, travel times — the path with the fewest edges is not necessarily the cheapest or fastest.

Example: given three routes from A to D:

• A → D directly: 1 edge, weight 20
• A → B → D: 2 edges, total weight 14
• A → C → D: 2 edges, total weight 5

BFS minimises edge count, so it returns A → D (1 edge — the fewest). But A → D costs 20. The genuinely shortest path by total weight is A → C → D at cost 5 — a 2-edge route that BFS would not select, because BFS does not consider edge weights at all. Dijkstra's algorithm solves this by tracking accumulated cost rather than hop count.

Dijkstra's algorithm solves the single-source shortest path problem on weighted graphs with non-negative edge weights. Given one source vertex, it finds the shortest path from that source to every other vertex in the graph.

In AQA exams, you will not be asked to recall the steps of Dijkstra's algorithm from memory. You will be given a partially completed working table and asked to continue or complete the trace. Understanding the logic of each step — not rote recall — is what the exam tests.

The algorithm maintains a tentative distance for each vertex: the shortest distance found so far from the source. Initially, only the source has a known distance (zero); all others are set to infinity.

At each step, the algorithm:

1. Selects the unvisited vertex with the smallest current tentative distance — call it the current vertex
2. For each unvisited neighbour of the current vertex: calculates the distance from the source via the current vertex. If this is smaller than the neighbour's recorded tentative distance, updates it
3. Marks the current vertex as permanently visited — its recorded distance is now confirmed as the shortest possible

The algorithm terminates when all vertices have been permanently visited (or when the destination vertex is confirmed, if only one shortest path is needed).

Why this works — the greedy property: Once a vertex is marked permanently visited, no shorter path to it can be discovered later. This holds as long as all edge weights are non-negative. A vertex with a tentative distance of 5 cannot be reached more cheaply via a vertex with tentative distance 8, because all edges from that vertex add further non-negative weight.

The worked trace uses this weighted undirected graph:

Edge	Weight
A–B	4
A–C	2
B–C	1
B–D	5
C–D	8
C–E	10
D–E	2

Goal: find the shortest path from A to every other vertex.

Initial state:

Vertex	A	B	C	D	E
Tentative distance	0	∞	∞	∞	∞
Visited	—	—	—	—	—

The source vertex A starts with distance 0. All others begin at infinity — meaning no path is yet known.

Tracking predecessors: alongside each tentative distance, record which vertex the update came from. This allows the shortest path to be reconstructed at the end by working backwards.