Dijkstra's algorithm

Greedy

Shortest distances from one source node to every node of a graph with non-negative weights, using a priority queue.

Dijkstra's algorithm starts at the source node and makes nodes "final" in order of their distance from the source. In each round it picks, among the nodes that are not final yet, the one with the smallest current distance. Because every weight is non-negative, no other path can later make that node's distance smaller, so its distance is settled.

Read the full explanation ↓

Time: O((V + E) log V)
Space: O(V + E)
CLRS, section 22.3
Horowitz–Sahni, chapter 6
Johnsonbaugh, chapter 8
Grimaldi, chapter 13

Input:

V=6 · E=8 · src=APDF export

A six-node directed graph where the shortest path to B goes through C, not along the direct edge A → B.

from heapq import heappop, heappush
INF = float("inf")
def dijkstra(graph, src):
dist = {v: INF for v in graph}
prev = {v: None for v in graph}
dist[src] = 0
pq = [(0, src)]
done = set()
while pq:
d, u = heappop(pq)
if u in done:
continue
done.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heappush(pq, (dist[v], v))
return dist, prev

Invariant: For every node in done, dist already holds the true shortest distance from the source.

Start

Final
Current node (u)
Shortest-path tree so far
Edge being checked

Priority queue `pq`

empty

Local variables

src'A'

Orange = changed in this step

graph dict

'A': [('B', 4), ('C', 2)]
'B': [('D', 5)]
'C': [('B', 1), ('E', 10)]
'D': [('E', 3), ('F', 6)]
'E': [('F', 2)]
'F': []

Call stack

dijkstra()line 6

Step 1 of 90

How the work grows with input size

Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

comparisons
relax
current input (n=6)

Show as a table

n	comparisons	relax
4	5.2	3.2
8	13.8	8
12	20.8	12
16	28	16.6
20	35.4	21.6
24	37.2	23.8
28	47.2	28.8

Explanation

The idea

The steps

Every node's distance is ∞ and the source's distance is 0. The source goes into the priority queue.
The node with the smallest distance is taken out of the queue (pop). If it was already final, it is skipped.
The node becomes final and is added to done.
For each outgoing edge u → v with weight w, check whether going through u reaches v sooner. If it does, dist[v] goes down (this is called relaxing the edge), prev[v] = u is recorded, and v goes into the queue with its new distance.
Repeat from step 2 until the queue is empty.

At the end, dist holds the shortest distance to every node, and following prev backwards from any node gives the path itself.

Why negative weights are not allowed

With a negative edge, a shorter path through that edge could appear after a node has already been made final, so the distance treated as settled would be wrong. For negative weights, use Bellman–Ford instead.

Notes on this implementation

The priority queue is Python's heapq, holding (dist[v], v) pairs: a distance and a node name. When two distances are equal, the node name decides which comes out first, so every run is the same.
Instead of decreasing a key inside the queue, each improvement pushes a new entry, and stale entries are recognised through done and skipped when they come out. This is simpler and keeps the cost at O((V + E) log V).

What to watch in the trace

The number next to each node is its dist. When an edge is relaxed, the change is highlighted.
In the "textbook-style example", watch dist[B] first become 4, then drop to 3 once C is final.
Compare the number of relaxations in the "worst case" input with the "best case".