Why does Dijkstra not work with negative edges
Why does Dijkstra not work with negative edges? It settles a node the moment it leaves the heap, and a negative edge can make a later path cheaper. Here is a four-node counterexample, the exact failure, and what to use instead.
The question of why does Dijkstra not work with negative edges has a one-sentence answer: the algorithm finalises each node when it leaves the heap, assuming no later path can be cheaper, and a negative edge makes that assumption false. A node gets locked in at the wrong distance and is never revisited.
That sentence is correct, but it is also easy to nod along to and forget. This essay makes it concrete: the line of the proof that breaks, a four-node graph where the answer comes out wrong, the tempting fixes that do not work, and the algorithms you should reach for instead.
What does Dijkstra assume when it takes a node off the heap?
It assumes the distance attached to that node is already the true shortest distance, because every other unsettled node is at least as far away and every edge still to be walked can only add to the total. The second half of that sentence is the one that matters.
Here is the invariant in plain terms. At any moment the algorithm has a settled set, the nodes whose distances it has declared final, and a heap of tentative distances for the frontier. It pops the frontier node u with the smallest tentative distance d(u). Why is d(u) the real answer? Take any other route from the source to u. That route starts inside the settled set and must cross to the outside at some point, through an edge that lands on a frontier node w. By the choice of u, the tentative distance of w is at least d(u). The route then continues from w to u, and the rest of the journey adds some amount. If every weight is nonnegative, that amount is zero or more, so the whole route costs at least d(u). No rival route can beat the one the heap already knows.
Read that argument again and find the line where weights enter. There is exactly one: the claim that the remainder of the route adds a nonnegative amount. Everything else is bookkeeping about the heap. So nonnegativity is not a technicality that textbooks mention for safety. It is the single load-bearing beam. Remove it and the proof does not degrade gracefully; it simply has no support. If you want the full proof laid out step by step, the Dijkstra invariant page walks through it.
Here is a framing I find useful. Think of Dijkstra as an auditor who signs off on a ledger line the moment it reaches the top of the pile, on the understanding that every other entry in the pile can only add cost. A negative edge is a late credit note that references a line already signed. The auditor has closed the books on that line and has no procedure for reopening it. The credit note is not ignored out of malice; the process simply has no step where a signed line is looked at again.
What does Dijkstra get wrong on a graph with one negative edge?
It reports a distance that is too large for every node whose cheapest route runs through the negative edge. You only need four nodes to see it.
Label the nodes S, A, B and C, with S as the source. The edges are: S to A with weight 2, S to B with weight 3, B to A with weight -2, and A to C with weight 1. By hand, the cheapest way to A is S to B to A, costing 3 + (-2) = 1, which beats the direct edge at 2. The cheapest way to C is then 1 + 1 = 2.
Now the textbook version, with a settled set:
import heapq
def dijkstra(graph, src):
dist = {v: float('inf') for v in graph}
dist[src] = 0
done = set()
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if u in done:
continue
done.add(u)
for v, w in graph[u]:
if v not in done and d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return distTrace it. Pop S at distance 0 and settle it; A gets 2 and B gets 3. The heap now holds (2, A) and (3, B). Pop A at 2, settle it, and relax A to C: C gets 3. The heap holds (3, B) and (3, C). Pop B at 3 (the tie breaks on the label), settle it, and try to relax B to A. But A is in the settled set, so the edge is skipped. Pop C at 3. The final answer is A = 2, B = 3, C = 3.
The true answers are A = 1 and C = 2. Two of the four nodes are wrong, and nothing in the run signalled a problem. That silence is the dangerous part. The algorithm does not crash or loop on a negative edge; it returns plausible numbers. In a real system that means a routing table or a cost estimate that is quietly off by a little, which is much worse than an exception.
Notice also that the error propagates. A was settled too early, so everything computed from A inherited the mistake. A single negative edge near the source can corrupt a large part of the graph, while a negative edge deep in a region that is settled last may do no harm at all. This is why the behaviour looks inconsistent in practice, and why people sometimes claim that Dijkstra works on their graph with negative edges. It works on their inputs by accident of ordering, and it is not a guarantee.
Does letting nodes be revisited fix Dijkstra with negative edges?
Partly. If the graph has no negative cycle you can get correct distances by allowing a settled node to be improved and pushed again, but you lose the running time guarantee that made Dijkstra worth using.
Many popular implementations do not keep a settled set at all. They push a new heap entry whenever a distance improves, and on popping they skip an entry only if it is stale, meaning its distance is larger than the current best for that node. Run that lazy version on the four-node graph. B is popped at 3 and relaxes A down to 1, pushing (1, A). A is popped again, relaxes C down to 2, and the answer comes out right. So the implementation detail decides whether the code is wrong or right on this input. That is worth knowing, because it explains why two people can both say they wrote Dijkstra and disagree about negative edges.
But look at what you have built. A node can now be popped many times. The usual argument that each edge is relaxed once, giving O((V + E) log V), is gone. In the worst case the number of pops can grow exponentially in the number of nodes; adversarial graphs for this exact scheme have been known since the 1970s. On benign inputs it runs fast, on a hostile one it stalls, and you cannot tell in advance which one you were given.
Negative cycles are worse. Suppose a loop of edges sums to -1. Every lap lowers the distances along it by 1, the heap always has something smaller to pop, and the program never terminates. There is also no correct answer to return, since the shortest path is undefined when you can keep shaving cost by walking in circles.
What the lazy, revisiting version really is has a name: a label-correcting algorithm. Bellman-Ford is the disciplined member of that family. It gives up the greedy ordering and instead repeats a full relaxation pass over all edges, V - 1 times, which is enough because a shortest path without cycles has at most V - 1 edges. A V-th pass that still improves something proves a negative cycle exists. You pay for the safety, but you buy a bound.
Why can't I just add a constant to every edge to make them positive?
Because adding a constant penalises each path in proportion to how many edges it has, so it changes which path is shortest. Paths with many edges get punished more than paths with few.
Test it on the same graph. The most negative edge is -2, so add 2 to every weight. S to A becomes 4, S to B becomes 5, B to A becomes 0, and A to C becomes 3. Now compare the two routes to A. The direct edge costs 4. The route through B costs 5 + 0 = 5. The direct edge wins, which is the opposite of the truth. The two-edge route absorbed +4 while the one-edge route absorbed only +2, and that gap flipped the order. Dijkstra on the shifted graph would run flawlessly and hand back the wrong shortest path.
There is a correct way to remove negative weights, and it is the heart of Johnson's algorithm. Instead of the same shift on every edge, give each node a potential h and replace each weight with w'(u, v) = w(u, v) + h(u) - h(v). Along any path from s to t the h terms telescope, so every path changes by exactly h(s) - h(t), a number that does not depend on the path. Order is preserved. You choose h as the shortest distance from a virtual source connected to every node by a zero edge, which you compute once with Bellman-Ford.
On our graph: h(S) = 0, h(B) = 0, h(A) = -2 (through B), h(C) = -1. The new weights are S to A: 2 + 0 + 2 = 4; S to B: 3 + 0 - 0 = 3; B to A: -2 + 0 + 2 = 0; A to C: 1 - 2 + 1 = 0. All nonnegative. Dijkstra from S now finds A at distance 3 through B, against 4 direct. Convert back by subtracting h(S) - h(A) = 2: the true costs are 1 and 2. The correction matches the hand calculation, and the constant shift would have broken it.
What should I use instead when edges can be negative?
Use Bellman-Ford for a single source with arbitrary weights, a DP in topological order if the graph is acyclic, and Johnson's algorithm if you need all pairs on a sparse graph. Which one is right depends on the graph's shape and size.
| Algorithm | Negative edges | Negative cycles | Time | Reach for it when |
|---|---|---|---|---|
| BFS | No (unit weights only) | Not applicable | O(V + E) | Every edge costs the same |
| Dijkstra, binary heap | No | Undefined behaviour | O((V + E) log V) | All weights are nonnegative |
| Bellman-Ford | Yes | Detects them | O(V * E) | Mixed signs, single source |
| DP in topological order | Yes | Cannot occur (acyclic) | O(V + E) | The graph is a DAG |
| Johnson | Yes | Detects them | O(V * E + V^2 log V) | All pairs, sparse graph |
| Floyd-Warshall | Yes | Detectable on the diagonal | O(V^3) | All pairs, small dense graph |
Scale matters here, so put numbers on it. Take a graph with V = 100,000 nodes and E = 500,000 edges. Dijkstra costs roughly (V + E) log2 V, about 600,000 times 17, close to 10 million basic steps; that finishes in well under a second in a compiled language. Worst-case Bellman-Ford costs V times E, which is 5 times 10^10 steps. At a generous 10^9 simple operations per second that is about 50 seconds. In practice you stop early when a pass changes nothing, and real graphs often settle in a handful of passes, but you cannot lean on that in a contest or an interview. The factor between the two algorithms is about 5,000, and that factor is what you are paying for the ability to accept a negative weight.
The acyclic case deserves a mention because it is so often overlooked. If the graph is a DAG, negative weights are harmless, since there are no cycles to exploit. Sort the nodes topologically, then relax each node's outgoing edges in that order. Every node is final by the time you reach it because all its predecessors came earlier. That is linear time, cheaper than Dijkstra. The topological sort page covers the ordering, and it pairs naturally with this idea. Scheduling problems with penalties and rewards are often this shape without anyone saying so.
Negative cycles also show up in real work, not just in exercises. Currency arbitrage is the classic case: take the negative logarithm of each exchange rate, and a profitable loop of trades becomes a cycle of negative total weight. Bellman-Ford's extra detection pass is exactly the tool that finds it.
How should you answer this in a coding interview?
State the invariant, give the small counterexample, and name the replacement. That three-step answer shows you understand the algorithm rather than remembering a rule.
When an interviewer asks why Dijkstra needs nonnegative weights, do not stop at "because it is greedy". Say that once a node is popped its distance is treated as final, because any other route must pass through a frontier node that is at least as far and then add nonnegative cost. Then draw the four-node graph. I like the one in this essay because a single line of arithmetic (3 - 2 = 1, which beats 2) exposes the failure. Then say what you would switch to: Bellman-Ford if the graph is general, a DAG pass if it is acyclic. Mention that you would first check the problem constraints, because most graph problems that ask for shortest paths on a grid or a road network guarantee nonnegative weights, and in that case the heap version is exactly right.
Also be ready for the follow-up about unit weights. If every edge costs 1, the heap is wasted effort: a plain queue explores nodes in order of distance by construction. Weights limited to 0 and 1 can use a deque, pushing zero-cost neighbours to the front. Choosing the cheapest tool that the weights allow is the real skill. The BFS versus DFS decision page covers the unweighted side of that choice, and the heap as array page shows what the priority queue underneath Dijkstra is doing at each pop.
One habit I would encourage: whenever you use a greedy algorithm, write down the sentence that justifies the greedy step, and then look for the input that falsifies it. For Dijkstra the sentence is "the remainder of any route costs at least zero", and the falsifying input is a negative edge. The same exercise applies to every greedy procedure you will meet, and it is much faster than discovering the flaw in a failing test. For more graph material, the graphs topic collects the related problems.
Frequently asked questions
Does Dijkstra work if the graph has a negative cycle?
No. When a cycle has negative total weight, the shortest path to any node it can reach is undefined, because each lap lowers the cost further. A version that allows revisits will loop forever, and a version with a settled set will return distances that mean nothing.
Does Dijkstra work with zero-weight edges?
Yes. The proof only needs weights to be zero or larger, so zero-weight edges are fine and ties are harmless. The invariant says the remainder of a route adds at least nothing, and zero satisfies that.
Is Dijkstra safe if only the edges leaving the source are negative?
Yes. The source is popped first and settled at 0, and every edge after that is nonnegative, so the invariant holds from the second pop onward; this fails once a negative edge appears anywhere past the source. If you want to see exactly which step of the argument carries the weight, read the Dijkstra invariant page next and try to break each line yourself.