Dijkstra's Algorithm & A*: Finding the Shortest Path (OCR A-Level CS 2.3.1)
OCR A-Level CS 2.3.1: how Dijkstra's algorithm finds the shortest path in a weighted graph, how A* improves it with a heuristic, and how to trace them.
Free Dijkstra A Star revision resources (OCR A-Level Computer Science, 2.3.1)
We’ve made exam-style practice for this exact topic, free to download: Dijkstra A Star question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.
When edges have weights (distances, times, costs), breadth-first search isn't enough — you need a shortest-path algorithm. Spec point 2.3.1(f) includes Dijkstra's shortest-path algorithm and the A* algorithm. This is the last topic in the course, and a regular Paper 2 question: trace Dijkstra's, and explain how A improves on it with a heuristic*.
Dijkstra's algorithm
Dijkstra's algorithm finds the shortest (lowest-weight) path from a start node to every other node in a weighted graph (with non-negative weights). It works by always settling the nearest unvisited node next:
Give the start node a distance of 0 and every other node infinity (∞).
From the unvisited node with the smallest distance, look at each neighbour: if going via this node is shorter than the neighbour's current distance, update it (and record this node as the neighbour's previous node).
Mark the current node visited (its shortest distance is now final).
Repeat until all nodes are visited (or the destination is settled).
The recorded previous nodes let you trace the shortest path back.
Worked example: shortest path from A
Weighted graph: A–B = 4, A–C = 2, B–C = 1, B–D = 5, C–D = 8, C–E = 10, D–E = 2. Find shortest paths from A:
Node settled | Final shortest distance from A |
|---|---|
A | 0 |
C | 2 (A→C) |
B | 3 (A→C→B) |
D | 8 (A→C→B→D) |
E | 10 (A→C→B→D→E) |
Notice A→C→B = 3 beats the direct A→B = 4 — Dijkstra's finds it by settling C first (distance 2), then relaxing B to 3. The shortest path A→E is A → C → B → D → E, total 10.
The A* algorithm
A* ("A-star") is an improvement on Dijkstra's for finding the shortest path to a specific goal. Dijkstra's explores outward in all directions; A adds a heuristic — an estimate of the remaining distance to the goal — to steer the search towards the goal, so it usually explores far fewer nodes*.
At each step A* picks the node with the smallest value of:
f = g + h
where g = the actual distance from the start so far, and h = the heuristic estimate of the distance still to go (e.g. the straight-line distance to the goal). If the heuristic never overestimates, A is guaranteed to find the shortest path — but faster* than Dijkstra's because it doesn't waste time exploring away from the goal.
In effect: Dijkstra's is A* with a heuristic of zero. A* is what sat-navs and games use for routing.
Comparing the two
Dijkstra's | A* | |
|---|---|---|
Finds | Shortest paths from start to all nodes | Shortest path to one goal |
Guidance | None — explores by distance only | A heuristic estimate towards the goal |
Cost function | g (distance so far) | f = g + h |
Speed | Explores more nodes | Usually explores fewer (faster) |
Guarantee | Shortest path (non-negative weights) | Shortest path if h never overestimates |
Common exam mistakes
Forgetting the weights. These work on weighted graphs — that's why BFS isn't enough.
Settling the wrong node. Dijkstra's always settles the smallest current distance unvisited node next.
Not relaxing via shorter routes. A longer direct edge (A→B = 4) can be beaten by a cheaper indirect one (A→C→B = 3).
Mixing up g and h. g = distance so far; h = estimate to the goal; A uses f = g + h*.
Saying A* needs no good heuristic. A only guarantees the shortest path if the heuristic never overestimates*.
Quick recap
Dijkstra's algorithm: shortest path in a weighted graph; repeatedly settle the nearest unvisited node, relaxing neighbours' distances; gives shortest paths from the start to all nodes.
Trace it with a table of current shortest distances and previous nodes — a shorter indirect route (A→C→B = 3) can beat a direct edge (A→B = 4).
A* improves Dijkstra's for a single goal by adding a heuristic h: pick the node with the smallest f = g + h (g = distance so far, h = estimate to goal).
A explores fewer nodes (faster) and still finds the shortest path if h never overestimates*.
Dijkstra's = A* with h = 0. A* powers sat-nav and game routing.
Frequently asked questions
What does Dijkstra's algorithm do? Dijkstra's algorithm finds the shortest, lowest-weight path from a start node to every other node in a weighted graph with non-negative weights. It works by repeatedly settling the unvisited node with the smallest known distance and updating the distances of its neighbours if a shorter route is found.
How does Dijkstra's algorithm work? It sets the start node's distance to 0 and all others to infinity, then repeatedly takes the unvisited node with the smallest distance, relaxes each neighbour (updating its distance and previous node if going via the current node is shorter), and marks the current node as visited. This continues until all nodes are settled.
What is the A* algorithm? A* is a shortest-path algorithm that improves on Dijkstra's when searching for a specific goal. It adds a heuristic that estimates the remaining distance to the goal, so the search is steered towards the goal and usually explores far fewer nodes than Dijkstra's while still finding the shortest path.
What is the difference between Dijkstra's algorithm and A*? Dijkstra's explores outward in all directions using only the distance travelled so far (g), and finds shortest paths to all nodes. A* searches towards a single goal using f = g + h, where h is a heuristic estimate of the distance still to go, so it usually reaches the goal faster by exploring fewer nodes.
What is the cost function f = g + h in A*? In A, g is the actual distance from the start node to the current node, and h is the heuristic estimate of the distance from the current node to the goal. A always expands the node with the smallest f = g + h, which balances how far it has come with how far it still has to go.
When is A* guaranteed to find the shortest path? A is guaranteed to find the shortest path when its heuristic never overestimates the true remaining distance to the goal (an admissible heuristic). If the heuristic is zero everywhere, A behaves exactly like Dijkstra's algorithm.
