Bellman-Ford: Shortest Paths When Some Edges Subtract Instead of Add

Dijkstra's algorithm has a blind spot

Dijkstra's algorithm finds shortest paths efficiently, but it assumes every edge weight is non-negative — it greedily finalises the closest unvisited node first, on the assumption that no later discovery could possibly make an already-finalised path shorter. A negative edge weight breaks that assumption outright: a path that looked longer at first glance could still turn out shorter once it picks up a negative-weight edge later on. Bellman-Ford, developed independently by Richard Bellman and Lester Ford in the 1950s, handles negative weights correctly by giving up Dijkstra's greedy shortcut and instead repeatedly relaxing every edge in the graph.

Relaxation, repeated exactly V-1 times

Relaxing an edge (u, v) with weight w means: if the best known distance to u, plus w, is less than the best known distance to v, update v's distance to that better value. Bellman-Ford's entire algorithm is: initialise the source's distance to 0 and everything else to infinity, then relax every edge in the graph, and repeat that full pass V-1 times, where V is the number of vertices.

dist[source] = 0;  dist[all others] = Infinity
repeat (V - 1) times:
  for each edge (u, v, w) in the graph:
    if dist[u] + w < dist[v]:
      dist[v] = dist[u] + w
// one more pass to check for negative cycles:
for each edge (u, v, w):
  if dist[u] + w < dist[v]:  report "negative cycle reachable from source"

Why V-1 passes exactly? A shortest path between any two vertices, if one exists and the graph has no negative cycle, visits at most V-1 edges (a path visiting more than that would have to repeat a vertex, meaning it contains a cycle, and removing that cycle can only shorten the path in a graph with no negative cycles making it beneficial to keep). Each full pass over all edges is guaranteed to correctly extend at least one more shortest path by one additional edge, in the worst case propagating the correction one hop further down the longest possible shortest path per pass — so V-1 passes are sufficient to guarantee every shortest path, however many edges it needs, has been fully relaxed.

The bonus: detecting negative cycles for free

If a negative-weight cycle is reachable from the source, shortest paths through it are not well-defined at all — you could loop around the cycle indefinitely, each loop reducing the total path cost further, so the true shortest path is negative infinity. Bellman-Ford detects this for free with one extra relaxation pass after the main V-1: if any edge can still be relaxed on that additional pass, some shortest-path estimate has not converged, which is only possible if a negative cycle reachable from the source is corrupting it. This detection capability, not just tolerance for negative edges, is the other reason Bellman-Ford remains standard even though it is slower than Dijkstra.

The cost of generality: O(V·E) instead of O(E log V)

Dijkstra's algorithm with a binary or Fibonacci heap runs in roughly O(E log V) or better; Bellman-Ford's V-1 full passes over all E edges cost O(V*E), substantially slower on large, dense graphs. In practice this trade-off is usually worth it only when negative weights genuinely need to be represented, or where Bellman-Ford's other property matters: because it is a straightforward, uniform relax-every-edge loop with no priority queue, it parallelises and distributes far more naturally than Dijkstra's inherently sequential greedy selection, which is exactly why distance-vector routing protocols like the original RIP protocol use a distributed variant of Bellman-Ford, where each router only needs to know its direct neighbours' distance estimates rather than the whole network topology.

Where negative weights come from in practice

Negative edge weights are not just a textbook curiosity: they appear whenever an edge represents a net gain rather than a pure cost, arbitrage detection in currency-exchange graphs where the log of an exchange rate can be negative and a negative cycle literally represents a profitable arbitrage loop, or in constraint-graph formulations of scheduling problems where an edge weight can encode a required time gap that is allowed to be negative. Bellman-Ford's negative-cycle detection is, in the arbitrage case, not an edge case to defend against — it is the actual answer the algorithm is being run to find.

Frequently asked questions

Try it live

Everything above runs in your browser — open Bellman-Ford and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.