Dijkstra's algorithm, explained

Dijkstra's algorithm answers the question every map app answers: what is the cheapest way to get from here to everywhere else? Edges have weights, such as distance or time.

It keeps a best-known distance for each node. It always finalises the closest unfinished node, then checks whether going through it gives any neighbour a shorter route.

How it works

• Set the start distance to 0 and every other distance to infinity.
• Pick the unfinished node with the smallest distance and mark it final.
• For each neighbour, check if going through this node is shorter than its current distance. If so, update it.
• Repeat until every node is final.

A small example

Take these weighted edges and start from A:

A-B:4  A-C:2  B-C:1  B-D:5  C-D:8  D-E:3

Distances from A:  A 0, C 2, B 3, D 8, E 11

B is reached faster through C (2 + 1 = 3) than directly (4).

What to know about its cost

• O(V²) as written in the experiment, and O((V + E) log V) with a priority queue.
• Uses O(V) space.
• Needs weights of 0 or more.

Where it works well

• Fast and reliable for shortest paths with non-negative weights.
• Gives the route to every node, not only one.

Where it struggles

• It can give wrong answers with negative weights.
• Only finds paths from one starting node at a time.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, D-E:3), choose Dijkstra and start from A, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment