Dijkstra's algorithm explained
The steps of Dijkstra's algorithm, a worked example traced in a table, and a robot that floods a mat to find the cheapest route round two walls. Change the costs, press Run, and see how it relates to A*, breadth-first search and negative weights.
Dijkstra's algorithm finds the cheapest route from one starting point to every other point in a graph, as long as no step costs less than nothing. Map apps use it and faster versions of it on road maps, internet routers use it to choose where to send data, and robots use it to plan a way round obstacles. On this page a small robot plans a route across a 2 metre mat with two walls in the way, and each demo below is a real program you can change and run.
On the mat, blue squares are cells the search has finished with, yellow squares are the frontier (cells it has found but not yet dealt with), and the red line is the route it chose. The chart shows the cost of each cell as the search finishes it.
The idea in one line
always finish the cheapest point you have not finished yet
That is the whole algorithm. Written out as steps:
- Give the start a distance of 0 and every other point a distance of infinity. Nothing is finished.
- Choose the unfinished point with the smallest distance, and mark it finished. Its distance can no longer change.
- For each neighbour of that point, work out the distance through it: its distance plus the cost of the step. If that is smaller than the neighbour's current distance, replace it, and note that the neighbour was reached from this point.
- Repeat from step 2 until every point is finished, or, if you only need one destination, until that one is.
- Read the route backwards: from the destination, follow where each point was reached from, back to the start.
The unfinished points with a distance are the frontier. Finding the smallest one quickly is the job of a priority queue.
A worked example
Five places, A to E, joined by roads with these lengths:
| Road | A-B | A-C | B-C | B-D | C-D | C-E | D-E |
|---|---|---|---|---|---|---|---|
| Length | 6 | 2 | 3 | 1 | 7 | 8 | 2 |
Find the shortest route from A to E. Each row of the table shows the distances after finishing one place, written as distance (reached from). Bold entries are finished.
| Step | Finish | A | B | C | D | E |
|---|---|---|---|---|---|---|
| start | 0 | ∞ | ∞ | ∞ | ∞ | |
| 1 | A | 0 | 6 (A) | 2 (A) | ∞ | ∞ |
| 2 | C | 0 | 5 (C) | 2 (A) | 9 (C) | 10 (C) |
| 3 | B | 0 | 5 (C) | 2 (A) | 6 (B) | 10 (C) |
| 4 | D | 0 | 5 (C) | 2 (A) | 6 (B) | 8 (D) |
| 5 | E | 0 | 5 (C) | 2 (A) | 6 (B) | 8 (D) |
- Step 2: C is finished before B because 2 is less than 6. Going A, C, B costs 2 + 3 = 5, less than the direct road at 6, so B changes to 5 (C).
- Step 3: through B, D costs 5 + 1 = 6, less than the 9 found through C.
- Step 4: through D, E costs 6 + 2 = 8, less than the 10 found through C.
Reading back from E: E from D, D from B, B from C, C from A. The shortest route is A, C, B, D, E, length 8. It uses four roads where A, C, E uses two, and it is still shorter. This is the table exam questions ask for, and the way to set one out by hand.
Dijkstra on the mat
On the mat the points are cells. The mat is cut into a 40 by 40 grid of 5 cm cells, each joined to its eight neighbours: a straight step costs 5 (centimetres) and a diagonal step 5 × √2, about 7.07. The walls are grown by 10 cm and any cell whose centre falls inside them is left out, so a route through the cells that remain keeps the robot's body clear of the walls. That leaves 1,020 cells the robot can reach. The robot is at the bottom left and the goal is the green corner at the top right.
The program
from bugbot import *
import heapq
import math
connect()
# change GOAL and press Run
GOAL = (34, 34) # the green corner
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
wait(0.1)
g = {START: 0} # cheapest cost found
came = {START: None} # the cell before
queue = [(0, START)] # (cost, cell) pairs
done = set()
while queue:
cost, cur = heapq.heappop(queue)
if cur in done:
continue # an old, dearer copy
done.add(cur) # cost is now final
if cur == GOAL:
break
if len(done) % 20 == 0:
plot("cost of the cell", cost)
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
new = cost + CELL * math.hypot(dx, dy)
if new < g.get(nxt, 1e9):
g[nxt] = new
came[nxt] = cur
heapq.heappush(queue, (new, nxt))
show()
route = []
c = GOAL
while c:
route.append(cm(c))
c = came[c]
route.reverse()
draw("route", route, "red", "line", 2)
print("cells expanded:", len(done))
print("route length:", round(g[GOAL]), "cm")
The chart is the cost of the cell being finished, sampled every 20 cells. It only ever goes up, from 12 to 330. That is the greedy rule at work: the queue always hands out the cheapest cell left, so no cell finished later can be cheaper than one finished earlier.
Dijkstra has no idea where the goal is, so it spreads evenly in every direction and stops only when the goal is finished. Here that meant 993 of the 1,020 reachable cells, because the green corner is one of the furthest points from the robot. A* adds a guess at the distance left to the goal and finds a route just as short on this mat after 662 cells.
Costs that are more than distance
A cost does not have to be a length. It can be time, fuel, money, or risk. Here, stepping into a cell within 20 cm of a wall (orange) costs three times its length. The algorithm does not change at all: only the price of a step does.
The program
from bugbot import *
import heapq
import math
connect()
# change NEAR_WALL and press Run
# 1: a step costs its length in cm
# 3: a step into a cell near a wall costs 3 times
NEAR_WALL = 3
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
GOAL = (34, 34) # the green corner
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def gap(c):
# how far cell c is from the nearest wall
x, y = cm(c)
near = 999
for wx, wy, ww, wh in WALLS:
dx = max(wx - x, 0, x - wx - ww)
dy = max(wy - y, 0, y - wy - wh)
near = min(near, math.hypot(dx, dy))
return near
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def price(c, step):
# the cost of stepping into cell c
if gap(c) < 20:
return step * NEAR_WALL
return step
# draw the dear cells, near a wall, in orange
dear = []
for i in range(40):
for j in range(40):
c = (i, j)
if gap(c) < 20 and not blocked(c):
dear.append(cm(c))
if NEAR_WALL > 1:
draw("near wall", dear, "orange", "squares", 5)
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
wait(0.1)
g = {START: 0} # cheapest cost found
came = {START: None} # the cell before
queue = [(0, START)] # (cost, cell) pairs
done = set()
while queue:
cost, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if cur == GOAL:
break
if len(done) % 20 == 0:
plot("cost of the cell", cost)
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
step = CELL * math.hypot(dx, dy)
new = cost + price(nxt, step)
if new < g.get(nxt, 1e9):
g[nxt] = new
came[nxt] = cur
heapq.heappush(queue, (new, nxt))
show()
cells = []
c = GOAL
while c:
cells.append(c)
c = came[c]
cells.reverse()
route = [cm(c) for c in cells]
draw("route", route, "red", "line", 2)
length = 0
for a, b in zip(route, route[1:]):
length += math.hypot(b[0] - a[0], b[1] - a[1])
print("cells expanded:", len(done))
print("route cost:", round(g[GOAL]))
print("route length:", round(length), "cm")
print("closest to a wall:",
round(min(gap(c) for c in cells)), "cm")
With NEAR_WALL = 1 the route is the plain shortest one, 337 cm, and it passes 12 cm from a wall. With NEAR_WALL = 3 it is 40 cm longer and never comes within 21 cm, and its cost is 377, the same as its length, because it avoids every orange cell. Try values in between: at 1.3 the short route still wins, at a cost of 373 against 377, and from 1.4 the route moves off the walls. Choosing the costs is most of the work in a real planner.
Every route at once
Take out the goal and let the search run until the queue is empty. It then knows the cheapest distance from the robot to every reachable cell, and the route to each one.
The program
from bugbot import *
import heapq
import math
connect()
# change these two places and press Run
A = (34, 34) # the green corner
B = (34, 6) # bottom right
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
BANDS = [("under 1 m", "green"),
("1 to 2 m", "cyan"),
("2 to 3 m", "blue"),
("over 3 m", "purple")]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def show():
# colour each finished cell by its distance
for k in range(4):
name, colour = BANDS[k]
pts = [cm(c) for c in done
if min(int(g[c] // 100), 3) == k]
draw(name, pts, colour, "squares", 5)
wait(0.1)
g = {START: 0}
came = {START: None}
queue = [(0, START)]
done = set()
# no goal this time: run until the queue is empty
while queue:
cost, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if len(done) % 25 == 0:
plot("cost of the cell", cost)
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
new = cost + CELL * math.hypot(dx, dy)
if new < g.get(nxt, 1e9):
g[nxt] = new
came[nxt] = cur
heapq.heappush(queue, (new, nxt))
show()
print("cells expanded:", len(done))
# every route is already there: follow
# came back from any cell to the robot
for end, colour in ((A, "red"), (B, "white")):
route = []
c = end
while c:
route.append(cm(c))
c = came[c]
draw("route " + colour, route, colour, "line")
print("to", end, round(g[end]), "cm")
The colours are rings of equal distance, bent round the walls. The two routes share their first part, because each cell remembers only the one cell it was reached from, so together the routes form a tree with the robot at its root. This is how a map app can show distances to many places, and how a network router builds a table of the best next hop to every other network.
Plan, then drive
A plan is only useful if the robot can follow it. This program plans with the wall costs from above, then drives the red line. The robot can move sideways as well as forwards, so it never needs to turn: it aims at a point on the route, and moves that point further along once it is within 8 cm.
The program
from bugbot import *
import heapq
import math
connect()
# change NEAR_WALL and press Run, then watch
# 1: a step costs its length in cm
# 3: a step into a cell near a wall costs 3 times
NEAR_WALL = 3
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
GOAL = (34, 34) # the green corner
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def gap(c):
# how far cell c is from the nearest wall
x, y = cm(c)
near = 999
for wx, wy, ww, wh in WALLS:
dx = max(wx - x, 0, x - wx - ww)
dy = max(wy - y, 0, y - wy - wh)
near = min(near, math.hypot(dx, dy))
return near
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def price(c, step):
# the cost of stepping into cell c
if gap(c) < 20:
return step * NEAR_WALL
return step
# draw the dear cells, near a wall, in orange
dear = []
for i in range(40):
for j in range(40):
c = (i, j)
if gap(c) < 20 and not blocked(c):
dear.append(cm(c))
if NEAR_WALL > 1:
draw("near wall", dear, "orange", "squares", 5)
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
wait(0.1)
g = {START: 0} # cheapest cost found
came = {START: None} # the cell before
queue = [(0, START)] # (cost, cell) pairs
done = set()
while queue:
cost, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if cur == GOAL:
break
if len(done) % 40 == 0:
plot("cost of the cell", cost)
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
step = CELL * math.hypot(dx, dy)
new = cost + price(nxt, step)
if new < g.get(nxt, 1e9):
g[nxt] = new
came[nxt] = cur
heapq.heappush(queue, (new, nxt))
show()
cells = []
c = GOAL
while c:
cells.append(c)
c = came[c]
cells.reverse()
route = [cm(c) for c in cells]
draw("route", route, "red", "line", 2)
print("route cost:", round(g[GOAL]))
# drive it: aim at a point on the route and
# move that point on as the robot comes near
i = 0
while True:
px, py = position() # cm from the start
x, y = 30 + px, 30 + py
tx, ty = route[i]
d = math.hypot(tx - x, ty - y)
if d < 8 and i < len(route) - 1:
i += 1
continue
if d < 2:
break
gx, gy = route[-1]
plot("cm from the goal",
math.hypot(gx - x, gy - y))
# a world velocity of up to 14 cm/s
s = min(14, 1 + 2 * d) / d
vx = (tx - x) * s
vy = (ty - y) * s
# turn it into the robot's own frame
a = math.radians(heading())
fwd = vx * math.sin(a) + vy * math.cos(a)
side = vx * math.cos(a) - vy * math.sin(a)
# 100 % is 20 cm/s forward, 15 sideways
turn = (heading() + 180) % 360 - 180
drive(fwd * 5, side * 6.7, -turn)
wait(0.1)
stop()
print("stopped at", round(x), round(y))
Set NEAR_WALL = 1 and it drives the shorter route instead, arriving after about 28 seconds with its centre 11 cm from a wall at the closest. position() is the overhead camera in the simulator, so the robot always knows where it is. A real robot has to work that out from its own sensors.
Dijkstra in Python
Here is the worked example above as a program. heapq keeps a list as a priority queue: heappop always removes the smallest (distance, place) pair.
import heapq
roads = {
"A": {"B": 6, "C": 2},
"B": {"A": 6, "C": 3, "D": 1},
"C": {"A": 2, "B": 3, "D": 7, "E": 8},
"D": {"B": 1, "C": 7, "E": 2},
"E": {"C": 8, "D": 2},
}
def dijkstra(graph, start):
dist = {start: 0}
prev = {start: None}
queue = [(0, start)]
done = set()
while queue:
d, v = heapq.heappop(queue)
if v in done:
continue # an old, dearer copy
done.add(v)
for w, cost in graph[v].items():
new = d + cost
if new < dist.get(w, float("inf")):
dist[w] = new
prev[w] = v
heapq.heappush(queue, (new, w))
return dist, prev
dist, prev = dijkstra(roads, "A")
print(dist)
route, v = [], "E"
while v is not None:
route.append(v)
v = prev[v]
print(route[::-1], dist["E"])
It prints each place's distance (A 0, B 5, C 2, D 6, E 8), then the route A, C, B, D, E and its length 8, the same as the table. When a shorter distance to a place turns up, the program pushes it again rather than changing the old entry, so a place can be in the queue twice. The dearer copy comes out later and is skipped, which is what done is for.
Why negative costs break it
The greedy rule relies on one fact: once a point is the cheapest unfinished one, no other route can reach it more cheaply, because every other route goes through a point that is already at least as expensive, and adding steps can only add cost. A negative step breaks that. With A to B costing 2, A to C costing 3 and C to B costing -2, Dijkstra finishes B at 2, but A, C, B costs 1. For graphs with negative costs, use the Bellman-Ford algorithm instead.
How fast it is
With V points and E edges, finding the cheapest unfinished point by searching a plain list takes O(V) each time, V times over: O(V²). With a binary heap as the priority queue, as in the program above, it is O((V + E) log V), which is much faster on maps where each point has only a few neighbours, like road maps and grids.
Questions
What are the steps of Dijkstra's algorithm?
Set the start's distance to 0 and every other distance to infinity. Repeatedly finish the unfinished point with the smallest distance, and for each of its neighbours, if the distance through this point is smaller than the one recorded, replace it and note where it came from. Stop when the destination is finished, then read the route backwards.
How do you trace Dijkstra's algorithm in a table?
Use one column per point and one row per point finished. In each row, write every point's current distance and the point it was reached from, and mark the finished ones. Show every time a distance goes down, not just the final values, then read the route back from the destination using the "reached from" entries.
Is Dijkstra's algorithm greedy?
Yes. At every step it takes the cheapest unfinished point and never goes back on that choice. For this problem the greedy choice is always right, as long as no cost is negative, which is why Dijkstra always finds the shortest route.
Is Dijkstra BFS or DFS?
It is closest to breadth-first search (BFS). BFS takes points from a plain queue in the order they were found. Dijkstra takes them from a priority queue in order of distance. When every step costs the same, the two finish points in the same order of distance and find routes with the same number of steps. It is nothing like depth-first search.
Does Dijkstra work with negative weights?
No. A negative edge can make a route through a later point cheaper than a point already finished, and Dijkstra never goes back to fix it, so it can give the wrong answer. The Bellman-Ford algorithm handles negative weights.
Where is Dijkstra's algorithm used?
In sat navs and map apps, where junctions are points and roads are edges weighted by distance or time. In internet routing, where link-state protocols such as OSPF have each router run Dijkstra over its map of the network to find the lowest-cost path to every other network. And in robots and games, for planning routes round obstacles, as on this page.
What is the difference between Dijkstra and A*?
Dijkstra orders its queue by the distance from the start. A* orders it by that distance plus a guess at the distance left to the goal, so it looks at fewer points when it only needs one route, and with the guess set to 0 the two are the same. On the mat on this page, for the same 337 cm route, Dijkstra expands 993 cells and the guess cuts that to 662.
What is the time complexity of Dijkstra's algorithm?
O(V²) when the next point is found by searching a list, and O((V + E) log V) with a binary heap as the priority queue, where V is the number of points and E the number of edges.
Is Dijkstra's algorithm on the A level Computer Science specification?
Yes. AQA's A level (7517) and OCR's A level (H446) both include Dijkstra's shortest path algorithm, and OCR also includes A*. Students trace it on a small weighted graph, usually in a table like the one on this page, and give applications such as route finding and network routing.
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- A4.1 Graphs Trees and graphs, A level
- A4.4 Breadth-first traversal Trees and graphs, A level
- A5.7 Dijkstra's shortest path algorithm Algorithms and complexity, A level
- U9.3 Dijkstra and the cost of a step Planning, University