Dijkstra's algorithm visualization

Dijkstra's algorithm finds the shortest path from one node to every other node in a graph whose edges have non-negative weights (lengths). It is greedy: it always finishes the closest node it has not finished yet, and it never has to revisit that decision.

How it works

1. Set the distance of the start node to 0 and every other distance to infinity. Put all nodes in a priority queue.
2. Take the unfinished node u with the smallest distance. Its distance is now final.
3. Relax each road from u to a neighbor v: if dist[u] + weight is less than dist[v], update dist[v] and remember prev[v] = u.
4. Repeat from step 2 until the queue is empty. Follow prev backwards from any node to read its shortest path.

The priority queue

A priority queue is a collection from which you always take out the item with the highest priority. Here the priority is the smallest distance. The lesson implements it in the simplest possible way: a list, scanned each time to find the minimum. A faster structure, the heap, has a lesson of its own.

A worked example of Dijkstra's algorithm

Use the Road map graph with start node A. The roads (and lengths) are A-B (7), A-C (2), C-B (3), B-D (1), C-E (5), D-F (4), E-F (2).

1. Finish A at 0. Update B ∞ to 7, C ∞ to 2. Queue: B:7 C:2 D:∞ E:∞ F:∞.
2. Finish C at 2. Update B 7 to 5, E ∞ to 7. Queue: B:5 D:∞ E:7 F:∞.
3. Finish B at 5. Update D ∞ to 6. Queue: D:6 E:7 F:∞.
4. Finish D at 6. Update F ∞ to 10. Queue: E:7 F:10.
5. Finish E at 7. Update F 10 to 9. Queue: F:9.
6. Finish F at 9. No update. Queue: empty.

Final distances: A 0, B 5, C 2, D 6, E 7, F 9. There were 14 edge checks and 7 updates. The queue is kept in node order, not sorted by distance; each round scans it for the smallest value. Two of the updates show why the algorithm relaxes roads instead of trusting the first distance it sees: B first gets 7 from the direct road but drops to 5 through C, and F first gets 10 through D but drops to 9 through E.

Dijkstra's algorithm pseudocode

G is the graph as adjacency lists, w(u, v) is the length of the road from u to v, and s is the start node.

DIJKSTRA(G, w, s)
1  for each node v in G
2      dist[v] = ∞
3      prev[v] = nil
4  dist[s] = 0
5  Q = the set of all nodes
6  while Q is not empty
7      u = the node in Q with the smallest dist[u]
8      remove u from Q
9      for each neighbor v of u
10         if dist[u] + w(u, v) < dist[v]
11             dist[v] = dist[u] + w(u, v)
12             prev[v] = u
13 return dist

Lines 10 to 12 are the relaxation. Line 7 is the priority queue: here a scan of Q, which costs O(V) per round and gives the O(V²) total. If the smallest dist[u] is ∞, every node left in Q is unreachable, and its relaxations change nothing.

Time and space complexity

With the simple list as a priority queue, each of the V rounds scans up to V nodes to find the minimum, and all the roads are relaxed once:

• Time: O(V²) with a list, because finding the minimum costs O(V) and it happens V times. A binary heap brings this down to O((V + E) log V), which matters on large sparse graphs.
• Space: O(V), for the distance table, the prev table and the queue.

When to use it, and when not to

• Use it for routes on a map, network latency, and any problem of the cheapest way from one place to the others.
• Use it only when all weights are zero or positive.
• If every edge counts the same, breadth-first search is simpler and enough.
• If some weights are negative, use an algorithm built for that, such as Bellman-Ford.

Where Dijkstra's algorithm is used

• Network routing. The link-state protocols OSPF and IS-IS give every router a map of the network. Each router runs a Dijkstra shortest-path-first calculation, with link costs as weights, to build its own routing table.
• Route planning on maps. Navigation software starts from Dijkstra's idea. Plain Dijkstra explores too many roads on a map the size of a continent, so routing engines add speedups, such as an A* distance estimate or preprocessing known as contraction hierarchies.
• Pathfinding in games and robots. When grid cells have different movement costs, such as road, grass and swamp, the cheapest route is a shortest path with weights. A*, a variant of Dijkstra's algorithm, is the common choice.

The weights must not be negative in any of them. Link costs, travel times and movement costs are all zero or positive.

Related algorithms and variations

With a binary heap as the priority queue the running time drops to O((V + E) log V). Fibonacci heaps, from Fredman and Tarjan (1984), bring it to O(E + V log V) in theory. If you only need the route to one target, you can stop as soon as that node leaves the queue. A* orders the queue by distance so far plus an estimate of the distance left, which steers the search toward the target. For negative weights, Bellman-Ford is the standard replacement.

When every edge has the same length, Dijkstra's algorithm behaves like breadth-first search (BFS vs Dijkstra), and the simpler algorithm is enough. Depth-first search finds some path instead of the cheapest (DFS vs Dijkstra).