Algorithms · Dijkstra

Dijkstra's algorithm

Why BFS fails once edges have weights, relaxing edges, the priority queue and lazy deletion, why negative edges break it, and how A star and Bellman-Ford relate.

Updated 2026-09-21

On this page

BFS finds the route with the fewest steps. Dijkstra finds the route with the lowest total cost — which is a different question as soon as the steps stop being equal. It is the same shape of algorithm with one part swapped: instead of always taking the node discovered earliest, always take the node that is currently cheapest.

The map

Read this first when short on time. Every branch is a section below.

Figure 1. The whole article on one page. Every branch is a section below; fold what you know, open what you do not.

Why BFS is not enough

BFS works because every edge costs one step, so "discovered earliest" and "closest" mean the same thing. Give the edges weights and that stops being true.

Figure 2. The direct edge is the shortest route in hops and the most expensive in cost. Once edges differ, "fewest steps" and "lowest total" are separate questions and BFS only answers the first.

The fix is to change what "next" means. BFS takes whatever was discovered earliest; Dijkstra takes whatever is currently cheapest to reach. That is the entire difference, and it turns the queue into a priority queue.

The idea

Keep a best-known cost for every node, starting at infinity except the source, which is 0. Repeatedly take the cheapest node you have not finished with, and check whether going through it improves any of its neighbours.

That check has a name, relaxing an edge, and it is one line:

if dist[u] + weight(u, v) is less than dist[v]:
        dist[v] = dist[u] + weight(u, v)

"Is the route to v through u better than the best route to v I already knew about?" If yes, write down the smaller number. Every node is in one of two states:

Tentative — the best cost found so far, which may still improve.
Settled — the node has been popped as the cheapest, and its cost is final and will never change again.

The algorithm is simply: settle the cheapest tentative node, relax its edges, repeat.

The algorithm

import heapq

def dijkstra(graph, start):               # graph[u] = list of (neighbour, weight)
    dist = {start: 0}
    parent = {start: None}
    pq = [(0, start)]                     # (cost so far, node)

    while pq:
        d, u = heapq.heappop(pq)          # the cheapest tentative node
        if d > dist.get(u, float('inf')):
            continue                      # stale entry, we already found better
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd              # relax
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent

Here it is on a small weighted graph — A→B 4, A→C 2, B→C 5, B→D 10, C→E 3, E→D 4, D→F 11:

Popped	What it relaxes	Heap after
A (0)	B = 4, C = 2	(2,C) (4,B)
C (2)	E = 5	(4,B) (5,E)
B (4)	C stays 2 (4+5 is worse), D = 14	(5,E) (14,D)
E (5)	D improves to 9	(9,D) (14,D)
D (9)	F = 20	(14,D) (20,F)
D (14)	stale — D is already settled at 9, skip	(20,F)
F (20)	—	empty

Final distances: A 0, C 2, B 4, E 5, D 9, F 20. Two details in that trace are worth pulling out.

Nodes come out in increasing cost order — 0, 2, 4, 5, 9, 20 — exactly as BFS produces nodes in increasing hop order. This is the same ring structure, measured in cost instead of steps.

The stale entry. D was pushed at 14 and later improved to 9, so the heap holds both. Rather than find and update the old entry, the algorithm pushes a new one and ignores the old when it surfaces — the if d > dist[u]: continue line. This is lazy deletion, and it is why the heap can hold more entries than there are nodes.

Cost is O(E log V): each edge can cause one push, and each heap operation is logarithmic.

Why it works, and where it breaks

The correctness argument is short and worth knowing, because it points directly at the one condition Dijkstra needs.

When the cheapest tentative node u is popped, could some other route reach it more cheaply? Any such route must leave the settled region through some other tentative node t. But u was the cheapest tentative node, so reaching t already costs at least as much as reaching u — and the rest of the route can only add more. So no cheaper route exists, and u's cost is final.

That last clause is the crux: the rest of the route can only add more. It holds only because edge weights are non-negative.

Figure 3. One negative edge is enough. Dijkstra settles B at 1 and never reconsiders it, so the cheaper route discovered afterwards is ignored and no error is raised.

Watch out

Dijkstra does not detect negative weights — it just returns wrong answers. If weights come from data you do not control (profit margins, elevation changes, adjustments that can go either way), either validate that they are non-negative or use Bellman-Ford, which handles them and reports negative cycles.

Practical points

Stopping early. If you only want the distance to one target, stop when that target is popped, not when it is first discovered. First discovery gives a tentative value that may still improve; popping is what settles it.

Rebuilding the path. Record a parent whenever you improve a node's distance, then walk parents back from the target and reverse — exactly as in BFS.

Lazy deletion versus decrease-key. The textbook version updates a node's existing heap entry, which needs a heap that supports decrease-key and a map from node to heap position. The lazy version just pushes a duplicate and skips stale entries. Lazy uses slightly more memory and is simpler, and in practice it is usually faster because the bookkeeping for decrease-key costs more than the extra pushes. Fibonacci heaps improve the theoretical bound and are almost never worth it in real code.

Tip

If every weight is a small integer, you can often beat the heap. Weights of only 0 and 1 give 0-1 BFS with a deque in linear time; small bounded weights allow a bucket queue with one bucket per distance value. The heap's log factor is worth removing when the weight range is tiny.

The family

Algorithm	Handles	Cost	Use when
BFS	Unweighted	O(V + E)	Every edge costs the same
0-1 BFS	Weights of 0 or 1	O(V + E)	A free move and a costly one
Dijkstra	Non-negative weights	O(E log V)	The default for weighted shortest paths
A star	Non-negative, plus a heuristic	Like Dijkstra, far fewer nodes in practice	One known target and a good estimate of remaining distance
Bellman-Ford	Negative weights	O(V × E)	Weights can be negative, or you need to detect a negative cycle
Floyd-Warshall	All pairs	O(V³)	Small graph, distances between every pair

A star deserves a sentence because it is the one most often needed. It is Dijkstra with the priority changed from "cost so far" to "cost so far plus an estimate of what remains". On a map, that estimate is straight-line distance, which points the search at the target instead of spreading in all directions. The estimate must never overestimate the remaining cost — otherwise the correctness argument above breaks and you can settle a node too early. Dijkstra is exactly A star with an estimate of zero.

Recap

BFS finds the fewest steps; Dijkstra finds the lowest total cost. They differ as soon as edges have different weights.
The only structural change is the queue: take the node that is currently cheapest rather than the one discovered earliest.
Relaxing an edge means asking whether the route through this node is better than the best route already known, and writing down the smaller number.
Nodes are tentative until popped, then settled and final. Nodes come out in increasing cost order, which is BFS's ring structure measured in cost.
Lazy deletion pushes a duplicate entry on improvement and skips stale ones when they surface, avoiding the need for a decrease-key heap.
The cost is O(E log V), where the log comes from the heap operations.
Correctness rests on the cheapest tentative node being unimprovable, because any alternative route starts with a prefix that already costs at least as much and can only grow.
That argument needs non-negative weights. A negative edge can improve a settled node, and Dijkstra never reconsiders one.
It fails silently on negative weights — no error, just wrong answers — so validate the input or use Bellman-Ford.
When targeting one node, stop when it is popped, not when it is first discovered.
Record a parent on every improvement to rebuild the path, exactly as in BFS.
With only 0 and 1 weights use 0-1 BFS and a deque; with small integer weights a bucket queue removes the log factor.
A star is Dijkstra plus an estimate of the remaining distance, and the estimate must never overestimate. Dijkstra is A star with a zero estimate.

Questions

Try answering each one out loud before opening it. Lead with the one-line answer, then the reasoning, then one detail that shows depth.

Why can't BFS be used on a weighted graph?

Because BFS assumes every edge costs the same, so "discovered earliest" equals "closest". With weights, a two-edge route can be cheaper than a one-edge route, and BFS would return the expensive short one.

BFS's rings correspond to hop counts, which stop matching cost once edges differ.
Dijkstra restores the property by ordering on cost rather than discovery order.
If all weights happen to be equal, Dijkstra degenerates to BFS with an unnecessary heap.

One trick worth knowing: an edge of weight k can be modelled as k unit edges, which makes BFS correct but blows up the graph.

What does relaxing an edge mean?

Checking whether the route to a neighbour through the current node is cheaper than the best route to that neighbour found so far, and recording the smaller value if it is.

It is the only place distances ever change.
Distances start at infinity for everything except the source, which starts at zero.
Recording a parent at the same moment is what lets the path be reconstructed.

The name comes from thinking of the distance estimate as a constraint being relaxed downward toward its true value.

What is the difference between a tentative and a settled node?

Tentative means the best cost found so far, which may still improve. Settled means the node has been popped as the cheapest remaining and its cost is final.

Only settled values can be trusted as answers.
This is why an early exit must trigger on popping the target, not on first discovering it.
The whole correctness proof is the claim that popping the cheapest tentative node settles it.

Mixing the two up is the most common source of off-by-one wrong answers in Dijkstra implementations.

Why is Dijkstra correct?

When the cheapest tentative node is popped, any alternative route to it must leave the settled region through some other tentative node — which already costs at least as much — and the remainder of that route can only add more. So no cheaper route exists.

The argument is a greedy exchange proof: assume a better route and show it cannot exist.
It depends entirely on the remainder being non-negative.
Nodes therefore settle in non-decreasing order of distance.

Understanding the proof is what makes the negative-weight restriction obvious rather than arbitrary.

What happens with a negative edge?

A node can be settled at one value and then a later, longer route through a negative edge turns out to be cheaper — but Dijkstra never revisits a settled node, so it returns a wrong answer with no error.

The failure is silent, which is what makes it dangerous.
Adding a constant to every weight does not fix it, because it penalises routes with more edges unequally.
Bellman-Ford handles negative weights and detects negative cycles, at O(V × E).

If weights derive from data you do not control, validating non-negativity up front is cheap insurance.

What is lazy deletion and why use it?

Instead of updating a node's existing heap entry when its distance improves, push a new entry and ignore the old one when it surfaces — detected by comparing the popped cost with the recorded distance.

It avoids needing a heap with decrease-key and a map from node to heap position.
The heap can hold more entries than there are nodes, bounded by the edge count.
In practice it is usually faster, because the bookkeeping for decrease-key costs more than the extra pushes.

Fibonacci heaps give a better theoretical bound and are almost never worth their constant factors in real code.

How do you stop early when you only want one target?

Return as soon as the target is popped from the heap, because that is the moment its distance becomes final — not when it is first discovered and pushed.

A node's tentative value at discovery can still improve later.
The saving can be large when the target is near the source in a big graph.
A star extends this idea further by biasing the search toward the target.

Stopping at first discovery is a subtle bug that produces correct answers on many test graphs and wrong ones on others.

What is the time complexity, and where does the log come from?

O(E log V) with a binary heap. Each edge can cause at most one push, and each push or pop costs logarithmic time in the heap size.

With lazy deletion the heap can hold up to E entries, so the log is technically log E, which is within a constant factor of log V.
A dense graph makes E close to V², so the bound approaches V² log V.
A simple array scan instead of a heap gives O(V²), which is actually better for very dense graphs.

That the naive array version wins on dense graphs is a useful reminder that the heap is an optimisation for sparse ones.

How does A star differ from Dijkstra?

The priority becomes cost-so-far plus an estimate of the remaining cost to the target, so the search is pulled toward the goal instead of expanding evenly in all directions.

The estimate must never overestimate the true remaining cost, or the correctness argument fails and nodes can settle too early.
Straight-line distance is the standard estimate on a map, and it is always a valid underestimate.
Dijkstra is exactly A star with an estimate of zero.

A better estimate explores fewer nodes, so the quality of the heuristic — not the algorithm — is where the performance comes from.

When would you use something other than a heap?

When the weight range is tiny. Weights of only 0 and 1 allow 0-1 BFS with a deque in linear time, and small bounded integer weights allow a bucket queue with one bucket per distance value.

Both remove the log factor entirely by exploiting the limited number of distinct priorities.
In 0-1 BFS a free edge goes to the front of the deque and a costly one to the back.
On very dense graphs, a plain array scan for the minimum beats a heap.

Checking the weight range before reaching for a heap is a quick win that is easy to overlook.

How would you find the shortest path in a graph where nodes, not edges, have costs?

Push the node cost onto its incoming edges — the cost of entering a node — and run Dijkstra normally, remembering to add the source's own cost to the starting distance.

Equivalently, split each node into an in-node and an out-node joined by an edge of that node's cost.
The splitting trick generalises to per-node constraints such as capacity or a visit limit.
Care is needed about whether the endpoints' costs count, which is usually a specification question rather than a technical one.

Node splitting is a standard way to turn node properties into edge properties so a standard algorithm applies.

Your graph has weights that change over time, such as traffic. What changes?

If the weight depends on when you arrive, the problem becomes time-dependent shortest path: distances are functions of arrival time rather than fixed numbers, and the state becomes a node plus a time.

Dijkstra still works if the network has the property that leaving later never lets you arrive earlier.
Without that property the greedy argument fails and the problem gets substantially harder.
Real routing systems precompute over the graph and apply live speeds as edge-weight updates rather than re-running from scratch.

This is where the gap between the textbook algorithm and a production routing engine is widest, and it is mostly about preprocessing rather than the search itself.