Why Does Dijkstra Fail With Negative Weights?

Why does Dijkstra fail with negative weights? Its key move is to take the smallest distance it knows about and declare that distance final. With nonnegative edges, a route that starts out more expensive cannot get cheaper as it continues. A negative edge breaks that reasoning. In a graph with just three nodes, Dijkstra can settle a node at distance 2 even though the shortest route to it costs only 1.
Three nodes and two routes
Start at node S. The other two nodes are A and B. Each edge has a direction, so you can follow it only from the first node listed to the second. These are the only edges:
| From | To | Weight |
|---|---|---|
| S | A | 2 |
| S | B | 5 |
| B | A | -4 |
The cost of a route is the sum of its edge weights. Going directly from S to A costs 2. Going from S to B and then to A costs 5 + (-4) = 1. Those are the only two routes from S to A, so the true shortest distance is 1. Here, shortest means lowest total weight, not fewest edges.
Notice that the graph has no cycle. Once you reach A, there is nowhere else to go, and there is no way back to S. The shortest distance is well defined. The problem is not that the answer keeps getting smaller as you go around a loop. It is that Dijkstra settles A before it has looked at the edge that makes the route through B cheaper.
The moment the wrong distance becomes final
Dijkstra keeps a tentative distance for each unsettled node. This is the cost of the best route to that node found so far, or infinity if no route has been found. Initially S has distance 0, and A and B both have distance infinity.
- Settle S at 0. Check its outgoing edges. The edge to A gives A a tentative distance of 2, and the edge to B gives B a tentative distance of 5.
- Settle A at 2. Of the unsettled nodes, A has the smaller tentative distance. Standard Dijkstra treats that choice as final. A has no outgoing edges, so this step discovers no new routes.
- Settle B at 5. The edge from B to A offers a route to A costing 5 + (-4) = 1. That is smaller than 2, but A has already been settled. An implementation that skips updates to settled nodes leaves A at the wrong distance.
If you run Dijkstra just to find the distance to A and stop when A is settled, you return 2 before ever checking B's outgoing edge. Running the usual settle-once version to the end does not fix its decision. If you are following along on paper, use separate columns for each node's tentative distance and whether it is settled. That distinction is also useful when you trace code by hand.
Why does Dijkstra fail with negative weights in the proof?
When Dijkstra selects A, it does not simply assume that the direct route is best. It relies on a rule about any route it has not finished exploring. Imagine walking along a competing route from S to A. There must be a first unsettled node on that route. The node immediately before it was already settled, so Dijkstra has already checked the edge into that first unsettled node.
Assume the distances settled before this step were correct. Then the tentative distance of that first unsettled node is at most the cost of the competing route up to that point: Dijkstra could reach the preceding node by a shortest route and then take the same edge. Also, A was chosen because it had the smallest tentative distance. So the cost of the competing route up to the first unsettled node is already at least A's tentative distance.
Here is where the weight restriction matters. If every remaining edge has weight zero or more, continuing along the route cannot lower its cost. The full competing route therefore cannot beat the distance Dijkstra is about to give A. The argument starts with S at distance 0 and applies again at each selection, which is why each settled distance stays correct.
In the three-node graph, the competing route first reaches an unsettled node at B. The cost so far is 5, which really is greater than 2. The comparison was not the error. The error was treating 5 as a lower bound on the cost of the completed route. The edge of weight -4 takes the total down to 1.
Change one edge and check the result
Replace the weight of B to A with 0. The route through B now costs 5, so settling A at 2 is safe. Zero weights are allowed because they can keep the total unchanged but cannot make it smaller. Now try -2 instead of 0. The route through B costs 3, so this particular run still gives the right answer. A negative weight removes the general guarantee; it does not mean every graph containing one produces a wrong result.
If a graph can have negative edges, one option is Bellman-Ford. Rather than declaring each node final the first time it looks best, it makes repeated passes over the edges so a cheaper route found later can still change a distance. It can also detect a negative-weight cycle reachable from the source. Such a cycle can be repeated to make the cost arbitrarily low for destinations reachable from that cycle.
For a paper exercise, try changing only the weight from B to A until the two routes tie, then decrease it by 1 and record the first incorrect decision. You can find more training and practice problems on the International Computer Science Competition site.
Frequently asked questions
Does Dijkstra work with zero-weight edges?
Yes. An edge of weight zero leaves the route cost unchanged, so it does not break the rule that extending a route cannot lower its cost.
Can Dijkstra fail even if there is no negative cycle?
Yes. The three-node example has no cycle at all, yet the edge from B to A makes a route cheaper after A has been settled.
At what weight do the two routes to A tie?
They tie when the edge from B to A has weight -3, because 5 + (-3) = 2.



