The algorithm, and the invariant that makes it correct
Give the source distance 0 and everything else infinity. Then repeat: take the unvisited node with the smallest tentative distance, mark it visited, and for each neighbour check whether going through this node is cheaper than the neighbour’s current best:
if dist[u] + weight(u, v) < dist[v]: dist[v] = dist[u] + weight(u, v)
That check is called relaxation. The key claim is that when a node is selected as the minimum, its distance is already final and will never improve.
Why? Any other route to it would have to leave the visited set through some unvisited node w. But w was not chosen, so dist[w] ≥ dist[u], and the rest of that route only adds more weight. So no cheaper route exists. This argument depends entirely on weights being non-negative — “the rest only adds more” is false if a later edge can subtract.
Work one through by hand
Edges: A→B (4), A→C (2), C→B (1), B→D (5), C→D (8), from A.
start: A=0, B=∞, C=∞, D=∞
pick A → relax: B=4, C=2
pick C (2, smallest) → relax: B = min(4, 2+1) = 3, D = 2+8 = 10
pick B (3) → relax: D = min(10, 3+5) = 8
pick D (8) → done
The shortest route to B is A→C→B at cost 3, not the direct edge at cost 4. Two hops beat one, which is exactly the case BFS gets wrong.
Shortest paths when edges have weights
BFS finds the path with the fewest edges. Dijkstra's algorithm finds the path with the lowest total cost, which is a different thing whenever edges differ in weight.
A three-edge route along quiet roads can be faster than a one-edge route along a jammed motorway. BFS would pick the motorway; Dijkstra picks correctly.
The algorithm is BFS with a priority queue instead of a plain queue:
- Set the start's distance to 0 and every other to infinity.
- Take the unvisited node with the smallest known distance.
- For each neighbour, if going through this node is cheaper than its current best, update it.
- Mark the node finished and repeat.
import heapq
def dijkstra(graph, start):
dist = {start: 0}
pq = [(0, start)] # (distance, node)
while pq:
d, node = heapq.heappop(pq)
if d > dist.get(node, float("inf")):
continue # a stale entry - skip it
for nbr, weight in graph[node]:
nd = d + weight
if nd < dist.get(nbr, float("inf")):
dist[nbr] = nd
heapq.heappush(pq, (nd, nbr))
return dist
The continue on line 8 is the detail that matters. Python's heapq has no decrease-key operation, so an improved distance is pushed as a new entry rather than updating the old one. The old entry is still in the heap, and skipping it when popped is what keeps the algorithm correct. This is called lazy deletion, and omitting the check produces subtly wrong results.
Why it needs non-negative weights
The algorithm's correctness rests on one claim: once a node is popped with the smallest tentative distance, that distance is final.
That holds because every edge adds a non-negative amount, so no path discovered later can be shorter. Any route to that node through an unvisited node would already be at least as long.
With a negative edge, the claim collapses. A node finalised at distance 5 might later be reachable at distance 2 via a negative edge from a node not yet processed — and Dijkstra never revisits it.
| Situation | Algorithm |
|---|
| Unweighted | BFS — O(V+E) |
| Non-negative weights | Dijkstra — O((V+E) log V) |
| Negative weights | Bellman-Ford — O(VE) |
| Negative cycles | Bellman-Ford, which detects them |
| All pairs | Floyd-Warshall — O(V³) |
| With a heuristic | A* — Dijkstra guided towards the goal |
Negative weights are not exotic: currency arbitrage, energy gained rather than spent, and rebates all produce them. Knowing that Dijkstra silently gives wrong answers there — rather than failing — is the practically important point.
Complexity, and what the heap buys
| Priority queue | Complexity |
|---|
| Unsorted array scan | O(V²) |
| Binary heap | O((V + E) log V) |
| Fibonacci heap | O(E + V log V) — theoretical |
The binary heap version is what everyone uses. Fibonacci heaps are asymptotically better and their constant factors are poor enough that they lose in practice.
The O(V²) array version is faster on dense graphs, where E approaches V², because it avoids the heap overhead. That is a real consideration for complete or near-complete graphs.
To recover the path rather than just the distances, record each node's predecessor when its distance is improved, and walk backwards from the goal.
Exploration guide
- Watch it expand by cost, not by distance on screen. Press Start Solver then Step repeatedly. The next node chosen is always the cheapest known, which is often not the nearest-looking one.
- Catch a relaxation. Keep stepping and watch a node’s distance drop when a better route is found. Every improvement is one relaxation, and once a node is finalised its number never changes again.
- Slow the expansion. Set Search Speed to 1 and press Auto. The visited set grows outward in rings of equal cost — that shape is Dijkstra exploring uniformly in every direction, which is precisely what A* improves on.
- Change the graph. Pick a different Network Topology, press Reset Grid, and run again. On a denser graph many more relaxations happen per node, because each node has more neighbours to improve.
Complexity, and why the priority queue matters
With a binary heap the cost is O((V + E) log V): each of V nodes is extracted once at O(log V), and each of E edges may trigger a decrease-key at O(log V).
With a naive array scan for the minimum it is O(V²), which is actually faster on dense graphs where E approaches V². With a Fibonacci heap the theoretical bound improves to O(E + V log V), though the constants are bad enough that binary heaps usually win in practice.
Traps worth knowing
- Using it with negative edge weights. The correctness argument fails and the algorithm returns wrong answers silently — a node finalised early may have a cheaper route through an edge considered later. Use Bellman-Ford, which handles negatives in O(VE) and detects negative cycles.
- Re-processing stale heap entries. Most implementations push duplicates instead of doing decrease-key. You must skip a popped node if it is already visited, or you will relax from an out-of-date distance.
- Forgetting the predecessor array. Dijkstra computes distances; reconstructing the actual route needs the parent pointer recorded on every successful relaxation.
- Running it to completion when one target is wanted. You can stop as soon as the target is popped — its distance is final at that moment. Continuing wastes the rest of the graph.
In one line
Dijkstra’s algorithm repeatedly finalises the cheapest unvisited node and relaxes its edges, giving single-source shortest paths in O((V + E) log V) with a binary heap. Its correctness rests on non-negative weights, so negative edges call for Bellman-Ford instead. Because it expands uniformly in all directions, it does more work than necessary when you only want one destination — which is the gap A* fills.
Where it is used
- Route planning. Every navigation system is Dijkstra or a derivative, with edge weights as travel time.
- Network routing. OSPF, a core internet routing protocol, runs Dijkstra over link costs.
- Flight and journey planning with cost, duration or number of changes as weights.
- Game pathfinding — usually A*, which is Dijkstra plus a heuristic.
- Dependency resolution with weighted preferences.
- Image processing — seam carving and intelligent scissors find minimum-cost paths through a pixel grid.
Real navigation systems do not run plain Dijkstra over a continental road network for every query — that would be too slow. They use precomputation: contraction hierarchies, which shortcut through unimportant nodes, or A* with a landmark-based heuristic. The underlying algorithm is still this one.
A*: the same algorithm with a hint
A* changes one thing. Instead of prioritising by distance from the start, it prioritises by
f(n) = g(n) + h(n)
where g is the known distance from the start and h is an estimate of the remaining distance to the goal.
That estimate focuses the search towards the goal rather than expanding uniformly in all directions, which on a large map is dramatically fewer nodes explored.
The condition for correctness is that h must be admissible — never overestimating the true remaining cost. Straight-line distance is admissible for road networks, because no road is shorter than the straight line.
With h = 0, A* is Dijkstra. With an overly optimistic heuristic it explores more; with an inadmissible one it may return a suboptimal path quickly, which is sometimes an acceptable trade.
Common mistakes
- Using it with negative weights. No error, wrong answer. Use Bellman-Ford.
- Forgetting the stale-entry check when using a heap without decrease-key.
- Marking nodes visited on push rather than on pop. A node's distance can improve while it sits in the queue.
- Confusing it with BFS on an unweighted graph. Dijkstra works there and BFS is simpler and faster.
- Comparing nodes in the heap. If distances tie, Python compares the second tuple element — so nodes must be comparable, or push a tiebreaking counter.
- Running it for a single target and not stopping. Break when the goal is popped; continuing computes distances you do not need.
Why it needs non-negative weights, on a graph where it fails
Every description of Dijkstra's algorithm mentions that edge weights must be non-negative. It is more convincing to build the graph that breaks it and watch the algorithm return a wrong answer confidently, because the failure is silent -- there is no error, just a shorter path it never looks at again.
Questions people ask
Why not BFS on a weighted graph? BFS minimises edge count, not cost. Three cheap edges can beat one expensive one.
What if weights are all equal? Use BFS — O(V+E) without the log factor.
How do I get the actual path? Store a predecessor for each node whenever its distance improves, then walk back from the goal.
Can I stop early? Yes — when the target is popped, its distance is final. Everything after that is unnecessary work.
Does it work on directed graphs? Yes, unchanged. Only follow outgoing edges.
What about several sources? Push all sources with distance 0. The result is each node's distance to the nearest source, in one run.
Recap in one screen
- Dijkstra is BFS with a priority queue: always expand the closest unfinished node.
- Its correctness depends on non-negative weights — with negatives it is silently wrong, so use Bellman-Ford.
- Use lazy deletion with
heapq: push improved distances and skip stale entries when popped. - O((V+E) log V) with a binary heap; the O(V²) array version wins on dense graphs.
- A* is the same algorithm prioritised by distance-so-far plus an admissible estimate of what remains.