Bellman-Ford: Shortest Paths with Negative Weights

Dijkstra's algorithm relies on the fact that adding another edge to a route can never make it cheaper. That holds whenever a weight is a distance or a duration, and it is what lets the algorithm lock in a node's cost and never look at it again, making for an efficient algorithm

But there are actually lots of instances where it makes sense for an edge to have negative weight. A currency trade can leave you holding more than you started with, a financial model can have a step that pays out, or a game can have a move that refunds. As soon as one weight is allowed to be negative, adding an edge really can make a route cheaper, and Dijkstra's license to stop looking is gone.

Dijkstra's algorithm wouldn't give an error when given negative weights, but usually the path it gives is not the best answer.

Dijkstra locks B in at 1 on its second step, because 1 is the smallest cost on the table at that moment. Only afterwards does it settle C at 2 and meet the C to B edge worth -2, which would have brought B down to 0. B is already finalised by then, and the algorithm will not reopen it. It reports 1 for B and 2 for D. The true answers are 0 and 1.

The damage was done at the moment of committing. Dijkstra's proof that a locked node is safe depends on every remaining route costing at least as much as the one it just took, and a single negative edge is enough to kill that guarantee.

The idea

Bellman-Ford's solution was simple but definitely not as efficient. It never works out a safe order to settle nodes in, so it never has to defend one. It relaxes every edge in the graph, then does the whole thing again, and again, until nothing improves. That's actually it, and you probably noticed that Bellman-Ford's algorithm is a lot easier to learn than Dijkstra's just slower.

Watching it work

Here is Bellman-Ford on the same graph Dijkstra just got wrong. The edge list beside the canvas is swept top to bottom, once per pass. Watch the fourth step in particular: B already holds a cost of 1, and the C to B edge drops it to 0 in the middle of that same pass.

Two things in that run are worth going back over. B improved twice, and the second improvement came from an edge whose source, C, had only just been given a value earlier in the very same sweep. Dijkstra cannot do that, because it works through nodes rather than edges, and a node it has finished with is closed for good.

The other is where it stopped. Pass 2 changed nothing at all, which means pass 3 would have read the same numbers and made the same comparisons, so the algorithm quit. A sweep that improves nothing proves the values have reached a fixed point. That raises the obvious question: this graph needed two passes, so how many could a graph possibly need?

Why V-1 passes

A shortest path never repeats a node. If it did, it would contain a loop, and cutting that loop out leaves a route that is no longer than the original and visits fewer nodes. So a shortest path touches at most V nodes, which means it uses at most V - 1 edges.

Now watch what one full sweep buys you. After the first sweep, every correct distance that needs a single edge is in place, because that edge got relaxed from a node whose cost was already right. After the second, every distance needing two edges is in place, since the one edge answers it builds on were correct. Each sweep locks in one more edge of depth, whatever order the edges happen to be listed in, so V - 1 sweeps settle everything.

That last clause is the whole trade. Dijkstra needs a carefully chosen order and pays for it with a heap and a correctness proof. Bellman-Ford needs no order at all and pays for it in time. The bound is a worst case rather than a schedule, which is why one boolean was enough to stop the run above two passes early.

When V-1 is not slack

It is fair to ask whether that worst case ever really happens. It does, and the shape that causes it is worth seeing once. Below is a plain five node chain, but its edge list is written back to front, so a sweep can only ever carry the frontier one hop further.

Pass 1 reaches B and stops, because by the time the sweep gets to the A to B edge it is the last one on the list and there is nothing after it to carry the new value onward. Pass 2 reaches C. It takes all four passes to reach E, which is exactly V - 1. Write the same four edges in the opposite order and the identical graph finishes in a single pass. The running cost depends entirely on an ordering the algorithm deliberately refuses to think about.

When there is no answer at all

There is a case where the question itself has no answer. If a cycle's weights sum to a negative number, you can lap it forever and get cheaper every time. Ask for the shortest path and there is no smallest value to hand back, because for any route you name there is a cheaper one.

Bellman-Ford catches this almost for free, and the reason is the bound you just proved. V - 1 passes are enough for every graph where shortest paths exist. So run one more. If any distance still improves on that extra sweep, no finite answer exists, because something must be looping to get cheaper.

The graph below has a loop through B, C and D worth -1 per lap. Run it and watch the distances keep sliding downward, then watch the extra pass catch them at it.

The outlined nodes are the cycle itself. You get them by following each node's best incoming route backwards until the trail closes on itself, and reporting which nodes are involved is usually far more useful to a caller than reporting that one exists somewhere.

That detector has uses well outside graph theory. Model currencies as nodes and exchange rates as edges, then weight each edge with the negative logarithm of its rate. Multiplying rates along a route becomes adding weights, so a negative cycle is a sequence of trades that hands back more than you put in. That is arbitrage, and finding it is the same computation you just watched.

What it costs

Up to V - 1 passes, each relaxing all E edges, so O(V * E) in the worst case. On a graph with ten thousand nodes and fifty thousand edges that is five hundred million operations, against roughly a million for Dijkstra on the same input.

The rule is plain. Use Dijkstra whenever you can, because it is far faster. Reach for Bellman-Ford when negative weights are genuinely possible, or when detecting a negative cycle is the actual goal.

The implementation

Notice the input. This one wants a flat list of edges rather than an adjacency list, since it never asks "what are this node's neighbors" and only ever sweeps every edge.

function bellmanFord(nodeCount, edges, source) {
  const dist = new Array(nodeCount).fill(Infinity);
  dist[source] = 0;

  // V-1 rounds: a shortest path uses at most V-1 edges.
  for (let round = 0; round < nodeCount - 1; round++) {
    let changed = false;
    for (const { from, to, weight } of edges) {
      if (dist[from] === Infinity) continue;
      if (dist[from] + weight < dist[to]) {
        dist[to] = dist[from] + weight;
        changed = true;
      }
    }
    if (!changed) break;              // settled early, common in practice
  }

  // One more round. Any improvement now means a negative cycle.
  for (const { from, to, weight } of edges) {
    if (dist[from] !== Infinity && dist[from] + weight < dist[to]) {
      return { dist: null, negativeCycle: true };
    }
  }

  return { dist, negativeCycle: false };
}

Where it goes wrong

Relaxing from a node that is still unreachable. Adding a weight to infinity gives nonsense, and in languages where infinity is a large integer it can overflow into a negative number and invent routes that do not exist. The if (dist[from] === Infinity) continue; line is not decoration.

Running V passes instead of V - 1, then wondering why cycle detection never fires. The detection pass has to be the extra one, run after the bound is exhausted. Fold it in and you lose the signal.

Reporting a negative cycle that cannot reach the source. A negative cycle in a far corner of the graph, unreachable from your start node, does not affect any distance you were asked about. If that distinction matters for your problem, check that the improving node is actually reachable.

Reaching for it by default because it is safer is a few hundred times slower on realistic inputs, and safety that costs that much is not free.

Check yourself