Dijkstra's algorithm

Your route planner knows the fastest way from your door to almost anywhere. At the heart of that idea is an algorithm Edsger Dijkstra worked out in about twenty minutes in 1956: grow outward from the start, and always finish the nearest place first.

A graph whose edges have lengths, with the nodes near the start finished in green, a tree of shortest routes, and a priority queue drawn underneath
A graph whose edges have lengths, with the nodes near the start finished in green, a tree of shortest routes, and a priority queue drawn underneath

The idea

Picture towns joined by roads of different lengths. The question is: what is the shortest way from my town to every other one? Breadth-first search answers it when every road counts the same, but here a route with more roads can be shorter. Dijkstra's algorithm keeps, for every town, the shortest distance found so far, and grows a region of towns whose distance is certain, always adding the nearest town that is not certain yet.

Step by step

Give the start distance 0 and every other node infinity. Put the start in a priority queue, a queue that always hands out the node with the smallest distance. Take that node; its distance is now final. For each neighbour that is not final, work out the distance through this node: its distance plus the edge's length. If that is shorter than the neighbour's distance so far, lower it, remember this node as the way there, and put the neighbour in the queue. This is called relaxing an edge. Repeat until the queue is empty, or until the goal is taken from it.

An example

Take the edges A–B of length 4, A–C 1, B–C 2, B–D 1, C–D 5 and D–E 3, and start at A. Taking A gives B distance 4 and C distance 1. C is nearest, so it is final at 1; through C, B drops to 1 + 2 = 3 and D gets 1 + 5 = 6. Now B is nearest, final at 3, and through B, D drops to 3 + 1 = 4. D is final at 4 and gives E 4 + 3 = 7. So the shortest way from A to E is A → C → B → D → E, length 7, even though A → B → D → E uses fewer edges and has length 8.

Why it is correct

Suppose node X is the nearest in the queue, at distance d. Any other way from the start to X must leave the region of final nodes at some point, and the first node it reaches outside that region is in the queue, so it is already at least d away. The rest of the way cannot make it shorter, because no edge is negative. So d is the shortest distance to X. With a negative edge that argument breaks; the Bellman–Ford algorithm, which relaxes every edge again and again, is used instead.

History and uses

Edsger W. Dijkstra designed the algorithm in 1956 to show off a new computer, the ARMAC in Amsterdam, by finding routes between Dutch cities, and published it in 1959. The same idea, with a smarter queue, runs in route planners and in internet routing protocols such as OSPF and IS-IS, which work out the shortest way for data to travel between routers. A* search adds a guess of the distance still to go, so it can head for the goal and look at fewer nodes.

Edsger W. Dijkstra at the blackboard
Edsger W. Dijkstra at the blackboard

Explore it

Open the app and press Step. The numbers on the edges are their lengths, and the number on each node is its distance so far. Nodes in the queue are blue, final nodes green, and the queue under the graph lists them nearest first, with their distances. Watch for the moments a distance drops because a longer-looking route turns out to be shorter, and pick a goal to see the search stop as soon as the goal is final.

Frequently asked questions

What is the time complexity of Dijkstra's algorithm?

It depends on the priority queue. With a simple list it is O(V²) for V nodes; with a binary heap O((V + E) log V) for E edges; with a Fibonacci heap O(E + V log V), as Michael Fredman and Robert Tarjan showed in 1984.

Can Dijkstra's algorithm handle negative edge weights?

No. It assumes a node's distance cannot improve once the node is the nearest in the queue, which a negative edge can break. Use the Bellman–Ford algorithm for graphs with negative edges.

Does Dijkstra's algorithm find the path to every node?

Yes. Run to the end, it gives the shortest distance from the start to every node that can be reached, and the remembered nodes form a tree of shortest paths. Stopping early when the goal is final saves work when only one path is needed.

How is Dijkstra's algorithm related to A*?

A* search is Dijkstra's algorithm with a hint: it orders the queue by the distance so far plus an estimate of the distance still to go, such as the straight-line distance on a map. With a good estimate it finds the same shortest path while looking at far fewer nodes.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try Dijkstra's algorithm