Definition
Dijkstra's Algorithm finds the shortest path between nodes in a weighted graph. It maintains a set of nodes whose shortest distance from the source is known.
How Dijkstra's Algorithm Works
pseudocode
procedure dijkstra(graph, source):
// Initialise distances
for each vertex v in graph:
distance[v] = INFINITY
visited[v] = False
end for
distance[source] = 0
while there are unvisited vertices:
// Pick unvisited vertex with smallest distance
current = vertex with minimum distance where visited[current] == False
visited[current] = True
// Update distances to neighbours
for each neighbour of current:
if not visited[neighbour] then
newDist = distance[current] + weight(current, neighbour)
if newDist < distance[neighbour] then
distance[neighbour] = newDist
end if
end if
end for
end while
return distance
end procedureKey Point
| Dijkstra aspect | Notes |
|---|---|
| Type | Greedy algorithm |
| Purpose | Shortest path from source in weighted graph |
| Requirement | Non-negative edge weights |
| Output | Shortest known distance to each reachable vertex |
| Core step | Action |
|---|---|
| 1 | Initialise source distance = 0, others = ∞ |
| 2 | Pick unvisited node with smallest tentative distance |
| 3 | Relax/update neighbour distances |
| 4 | Mark node visited |
| 5 | Repeat until all reachable nodes processed |
Worked Example: Tracing Dijkstra's Algorithm
Find the shortest path from A to F in a graph that has these edges.
| Edge | A–B | A–C | B–D | C–D | C–E | D–F | E–F |
|---|---|---|---|---|---|---|---|
| Weight | 3 | 4 | 6 | 2 | 5 | 4 | 7 |
Worked Example
Working: the unvisited node with the smallest distance is visited next
Final table
The path is read backwards from the end node using the previous-node column: F was reached from D, D from C and C from A.
Shortest path: A, C, D, F. Distance: 10.
| Node visited | Distance from A | Updates to its unvisited neighbours |
|---|---|---|
| A | 0 | B = 3 (from A); C = 4 (from A) |
| B | 3 | D = 3 + 6 = 9 (from B) |
| C | 4 | D = 4 + 2 = 6, which is less than 9, so D becomes 6 (from C); E = 4 + 5 = 9 (from C) |
| D | 6 | F = 6 + 4 = 10 (from D) |
| E | 9 | F through E would be 9 + 7 = 16, which is not less than 10, so F is unchanged |
| F | 10 | End node reached |
| Node | Distance from A | Previous node |
|---|---|---|
| A | 0 | None |
| B | 3 | A |
| C | 4 | A |
| D | 9, then 6 | B, then C |
| E | 9 | C |
| F | 10 | D |
Shortest path: A, C, D, F. Distance: 10.
Exam Tip
Show every distance a node has held, not only the last one, so that it is clear when a shorter route replaced a longer one (D: 9, then 6). Finish by stating both the path and its total distance.