Dijkstra Algorithm

Always lock in the closest unvisited vertex, then relax its edges

time O(V^2)space O(V)

Because every edge weight is non-negative, the unvisited vertex with the smallest tentative distance can never be beaten later by a longer path through something still unvisited — so it is safe to lock that vertex's distance in for good right now. That is the whole algorithm: repeatedly pick the closest unlocked vertex, freeze it, and use it to shrink its neighbors' distances (relaxation). The badge on each vertex below is its current best-known distance from the source; the highlighted vertex is the one just locked in, and the highlighted arrows show which distances it just improved.

Details

Animated on: 6 vertices, directed weighted edges 0->1(4), 0->2(1), 2->1(2), 1->3(1), 2->3(5), 3->4(3), 1->4(8), 4->5(2), 3->5(6), source = 0 — find the shortest distance from 0 to every other vertex.

Problem:Dijkstra AlgorithmMedium

Always lock in the closest unvisited vertex, then relax its edges

step 1 / 14

Distances start at infinity, source at 0

inf

Every vertex starts at infinity except the source, vertex 0, which starts at 0 — that is the only distance we know for certain before looking at a single edge.

Pseudocode

1FUNCTION dijkstra(graph, source):
2  dist[source] <- 0
3  FOR EACH v != source
4    dist[v] <- INFINITY
5  visited <- EMPTY SET
6  IF NO unvisited v WHERE dist[v] < INFINITY: RETURN dist
7  WHILE visited != ALL vertices
8    u <- unvisited v WITH MIN dist[v]
9    ADD u TO visited
10    FOR EACH (u, v, w) IN edges
11      IF dist[u] + w < dist[v]
12        dist[v] <- dist[u] + w
13  RETURN dist

← / → step · space play · Home restart

Every step in words

Show all 14 steps

Every vertex starts at infinity except the source, vertex 0, which starts at 0 — that is the only distance we know for certain before looking at a single edge.
Of everything still unvisited, vertex 0 has the smallest distance, 0. Non-negative weights mean no later edge can ever undercut that — lock it in as final and never revisit it.
Relax 0's outgoing edges: 0->1 costs 0+4=4, beating inf; 0->2 costs 0+1=1, beating inf. Update to the smaller total.
Of everything still unvisited, vertex 2 has the smallest distance, 1. Non-negative weights mean no later edge can ever undercut that — lock it in as final and never revisit it.
Relax 2's outgoing edges: 2->1 costs 1+2=3, beating 4; 2->3 costs 1+5=6, beating inf. Update to the smaller total.
Of everything still unvisited, vertex 1 has the smallest distance, 3. Non-negative weights mean no later edge can ever undercut that — lock it in as final and never revisit it.
Relax 1's outgoing edges: 1->3 costs 3+1=4, beating 6; 1->4 costs 3+8=11, beating inf. Update to the smaller total.
Of everything still unvisited, vertex 3 has the smallest distance, 4. Non-negative weights mean no later edge can ever undercut that — lock it in as final and never revisit it.
Relax 3's outgoing edges: 3->4 costs 4+3=7, beating 11; 3->5 costs 4+6=10, beating inf. Update to the smaller total.
Of everything still unvisited, vertex 4 has the smallest distance, 7. Non-negative weights mean no later edge can ever undercut that — lock it in as final and never revisit it.
Relax 4's outgoing edges: 4->5 costs 7+2=9, beating 10. Update to the smaller total.
Of everything still unvisited, vertex 5 has the smallest distance, 9. Non-negative weights mean no later edge can ever undercut that — lock it in as final and never revisit it.
None of 5's outgoing edges improve on a distance already recorded, so every neighbor keeps its current value.
All reachable vertices are locked in: [0, 3, 1, 4, 7, 9] from source 0. RETURN dist.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Dijkstra Algorithm in the editor All Graph problems Back to roadmap