The Bellman–Ford algorithm

Some shortest-path problems have edges that make a path cheaper: a refund, a downhill stretch, an exchange rate in your favour. Dijkstra's algorithm cannot cope with them. The Bellman–Ford algorithm can, by trading cleverness for patience.

A graph with one-way arrows, some edges negative, the distances found so far on the nodes, and a negative cycle drawn in red
A graph with one-way arrows, some edges negative, the distances found so far on the nodes, and a negative cycle drawn in red

The idea

Every shortest-path algorithm relies on one move, relaxing an edge: if going to u and then along the edge u → v is shorter than the best known way to v, use it. Dijkstra's algorithm relaxes each edge once, in a clever order that only works when no edge is negative. Bellman–Ford makes no such assumption. It relaxes every edge, in any fixed order, again and again, until the distances stop changing.

Step by step

Give the start distance 0 and every other node infinity. Repeat n − 1 times, for n nodes: go over every edge u → v and relax it if u has a distance. Stop early if a whole pass changes nothing. Then make one more pass. If any edge can still be relaxed, a cycle with a negative total can be reached from the start; otherwise every distance is the shortest, and the remembered nodes give the paths.

An example

Take one-way edges A → B of length 4, A → C 5, B → D 2 and C → B −3, checked in that order, from A. Pass 1 gives B 4, C 5 and D 6, and then C → B lowers B to 5 − 3 = 2. Pass 2 lowers D to 2 + 2 = 4. Pass 3 changes nothing, so the answer is B 2, C 5, D 4. Dijkstra's algorithm would have made B final at 4 and D at 6, before seeing the negative edge. Add an edge D → C of length −4, and the cycle C → B → D → C totals −5: every pass lowers the distances again, and the check pass reports it.

Why n − 1 passes are enough

A shortest path, when one exists, never repeats a node, so it has at most n − 1 edges. Relaxing every edge in a pass extends every correctly known shortest path by one more edge, whatever the order of the edges. So after pass k, all shortest paths with up to k edges are right, and after n − 1 passes, all of them. The order still matters for speed: a good order can finish in one or two passes.

History and uses

Alfonso Shimbel described the method in 1955, Lester Ford Jr. in 1956, Edward F. Moore in 1957 and Richard Bellman in 1958; it carries the names of two of them, Bellman and Ford. Its passes can be run by every router on its own, which made it the basis of distance-vector routing protocols such as RIP. In finance, taking the negative logarithm of exchange rates turns a profitable round of currency trades into a negative cycle, which Bellman–Ford can find.

Richard Bellman in 1962, photographed by Alfred Eisenstaedt. He published the shortest-path method in 1958, after Shimbel, Ford and Moore.
Richard Bellman in 1962, photographed by Alfred Eisenstaedt. He published the shortest-path method in 1958, after Shimbel, Ford and Moore.

Explore it

Open the app and press Step. Every edge is one-way, and some lengths are negative. Each step checks one edge, in a fixed order, and the tiles show the pass and how many distances it changed. Usually a pass soon changes nothing and the search stops early. Tick Add a negative cycle and watch the distances fall pass after pass until the check pass finds the cycle and draws it in red.

Frequently asked questions

What is the time complexity of Bellman–Ford?

O(V · E) for V nodes and E edges: up to V − 1 passes, each checking every edge. With early stopping it is often much faster in practice, and in the best case a single pass is enough.

What is a negative cycle?

A cycle whose edge lengths add up to less than zero. Going round it again and again makes a path as short as you like, so shortest distances to every node reachable through it are undefined.

Does Bellman–Ford work on undirected graphs?

Only if no edge is negative: an undirected negative edge can be crossed back and forth, which is a negative cycle of two edges. With non-negative edges it works, but Dijkstra's algorithm is faster.

What is SPFA?

The Shortest Path Faster Algorithm, a version of Bellman–Ford that only re-checks the edges out of nodes whose distance just changed, using a queue. It is often much faster, though its worst case is the same.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try Bellman–Ford