Dijkstra
Dijkstra keeps a tentative cost for every node and a priority queue ordered by that cost. It repeatedly takes the cheapest node in the queue, declares its cost final, and then relaxes every edge leaving it — offering each neighbour a cheaper route through the node just settled. The order of settling is by cost, not by arrival, which is the whole difference from breadth-first search.
Its frontier
A priority queue, smallest cost first.
When it is the right choice
Any shortest-path question where the edges cost different non-negative amounts: road distances, network latency, a weighted grid. It is the default for a reason — it settles each node once and touches each edge once. It cannot be used when an edge can be negative, and that is not a limitation to work around but a consequence of the argument that makes it correct.
How it works
- Give the source a cost of zero and every other node a cost of infinity.
- Put the source in the priority queue.
- Take the node with the smallest cost. Its cost is now final.
- For each edge leaving it, add the edge weight to the settled cost.
- If that is cheaper than the neighbour’s current cost, record it, remember the edge, and put the neighbour in the queue.
- Repeat until the queue is empty, or until the target has been settled.
Worth noticing
- Why a negative edge breaks it: Dijkstra declares a node final the moment it is taken from the queue, on the grounds that nothing left in the queue could reach it more cheaply. A negative edge makes that false — a longer route could still get cheaper later — so the answer would be wrong rather than slow. Load a graph with negative weights and this page refuses; Bellman-Ford runs on it.
- A node can be offered a cheaper route several times before it is settled, and the pushed counter climbing past the settled counter is that happening. Only the last offer survives.
- On the grid every edge costs one, so Dijkstra settles nodes in exactly breadth-first order. That is worth seeing: on an unweighted graph the two algorithms are the same algorithm.
Cost
- Best
- O(E + V log V)
- Average
- O(E + V log V)
- Worst
- O(E + V log V)
- Extra space
- O(V)
- Runs on
- a grid with walls; a weighted undirected graph; a directed acyclic graph; a directed graph with a cycle
- Largest grid
- 11 by 7 cells
- Largest graph
- 14 nodes, 28 edges
The limits are pedagogical rather than technical: this tool keeps a cost and a predecessor for every node in every recorded step, so the size of the graph sets the size of the trace directly, and a run has to stay short enough to sit and watch. A graph that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the number of nodes and edges rather than by running it and finding out.
Graphs are generated from a seed, so the link in your address bar draws exactly the graph on your screen — no part of it is random in a way a reload could change.