Skip to content
Tutorials Center
My learning

Topics

Lesson 135 of 225 ยท Shortest Paths and Spanning Trees

Bellman-Ford Algorithm

Learn Bellman-Ford step by step: relax every edge V-1 times, handle negative weights, detect and print negative cycles, and solve cheapest flights with k stops.

Dijkstra's algorithm is fast, but it makes one promise that fails the moment an edge has a negative weight: once it pulls a vertex out of the heap, that vertex's distance is final. With a negative edge somewhere later in the graph, a "final" distance can still be beaten. Negative weights are not exotic. They model refunds, discounts, energy that is recovered when going downhill, or the logarithm of an exchange rate. For these graphs you need an algorithm that never declares anything final too early.

Bellman-Ford is that algorithm. It is simpler than Dijkstra, needs no heap, works with negative edges, and as a bonus it tells you when the shortest path does not exist because a negative cycle lets you reduce the cost forever. The price is speed: O(VยทE) instead of O((V + E) log V). In this lesson you will see why the idea works, trace it pass by pass, detect and print negative cycles, and apply it to two classic problems.

Why Dijkstra breaks on negative edges

Dijkstra's greedy argument is "any other route to this vertex must go through vertices that are even farther away, so it cannot be shorter". A negative edge destroys that argument, because a longer route can finish with a big discount.

Python A Dijkstra-style greedy gets it wrong

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Vertex 1 was finalized with distance 2 before vertex 2 was even looked at. The real shortest route, 0 โ†’ 2 โ†’ 1, costs 1.

The idea: relax everything, repeatedly

Bellman-Ford does not try to be clever about order. It uses the same relaxation step as Dijkstra:

TEXT
relax(u, v, w):  if dist[u] + w < dist[v]:  dist[v] = dist[u] + w

and applies it to every edge, in any order, then repeats the whole sweep. The key fact:

After pass k, every vertex whose shortest path uses at most k edges already has its correct distance.

Why? Pass 1 fixes everything reachable by a one-edge path, because dist[source] is correct from the start. Suppose after pass k-1 the vertex u is correct. Then in pass k the edge (u, v) is relaxed and v becomes correct if its best path is k edges long. A shortest path never repeats a vertex (when there is no negative cycle), so it has at most V - 1 edges. Therefore V - 1 passes are enough.

TEXT
shortest path to 4:   0 --> 2 --> 1 --> 3 --> 4        (4 edges, V = 5)
correct after pass:    -     1      2      3      4

If the edges happen to be listed in a lucky order, vertices get fixed sooner, and a pass that changes nothing means we can stop early.

The algorithm in code

Python Bellman-Ford with parents and early exit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two details matter. First, we skip edges whose tail is unreachable (dist[u] != INF); otherwise we would add a weight to infinity, which is harmless in Python but overflows or gives nonsense in languages with an integer "infinity". Second, parent records which edge last improved each vertex, so following it backwards rebuilds the path, exactly as in Dijkstra.

Tracing the passes

To see the claim "after pass k paths with k edges are correct", we list the edges in the least helpful order, so each pass can only move information one step.

Python Pass-by-pass trace in the worst edge order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output down the columns. Vertex 2 is right after pass 1, vertex 1 after pass 2, vertex 3 after pass 3, and vertex 4 only after pass 4, which equals V - 1. This is the worst case: the answer needed every pass. With the edges in a friendlier order, the same graph would settle in fewer passes, and the early exit in the previous example would stop sooner.

Within a single pass, an update made earlier can already be used by a later edge. That only helps, so the guarantee "paths of at most k edges are correct after pass k" stays true, and sometimes the algorithm is faster than the guarantee.

Negative cycles

A negative cycle is a cycle whose weights add up to less than zero. Walk around it once and you are cheaper than before, so you can walk around forever and the "shortest" distance is minus infinity. In that case no shortest path exists for any vertex reachable from the cycle.

Bellman-Ford detects this for free. If no negative cycle exists, everything is settled after V - 1 passes, so a V-th pass cannot improve anything. If some edge still relaxes in pass V, there is a negative cycle reachable from the source.

To print the cycle, remember the last vertex improved in pass V. Follow parent V times to be certain you are standing inside the cycle (the improved vertex may only hang off it), then walk until you return to the starting vertex.

Python Finding and printing a negative cycle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Watch out: An undirected edge with a negative weight is itself a negative cycle (go there and back). Bellman-Ford on undirected graphs is only meaningful when all weights are non-negative, and then you should simply use Dijkstra.

Complexity

Each pass looks at all E edges and there are at most V - 1 passes (plus one for detection), so the time is O(VยทE). For a graph with 1,000 vertices and 10,000 edges that is about ten million relaxations in the worst case, which is fine. For a million vertices it is hopeless, which is why Dijkstra is preferred whenever weights are non-negative.

Time Space Negative edges Negative cycle detection
Bellman-Ford O(VยทE) O(V) yes yes
Dijkstra (binary heap) O((V + E) log V) O(V) no no
Floyd-Warshall (all pairs) O(Vยณ) O(Vยฒ) yes yes (diagonal)

Space is just the distance and parent arrays, O(V), plus the edge list you already have. Note that Bellman-Ford wants an edge list, which is one of the three graph representations; it never needs neighbor lookups.

A common speed-up is SPFA (queue-based Bellman-Ford): keep a queue of vertices whose distance just changed and only relax their outgoing edges. It is often fast in practice, but its worst case is still O(VยทE), and adversarial inputs exist, so treat it as an optimization, not a new bound.

Problem: cheapest flight with at most k stops

Here Bellman-Ford's "pass number equals edge count" property becomes the whole solution. Run exactly k + 1 passes (a route with k stops uses k + 1 flights), and in every pass relax from a copy of the previous distances. Without the copy, an update from this pass could be reused in the same pass and a path could use more edges than allowed.

A brute-force approach would try every route with depth-first search, which can take exponential time. The pass-limited Bellman-Ford needs only O(kยทE).

Python Cheapest flights within k stops

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 0 stops there is no direct flight, so the answer is -1. One stop allows 0 โ†’ 2 โ†’ 3 for 600. Two stops allow 0 โ†’ 1 โ†’ 2 โ†’ 3 for 300. A third stop changes nothing because no longer route exists. Dijkstra cannot answer this directly, since the cheapest route is not the one that may use few edges.

Problem: currency arbitrage

Exchange rates multiply along a chain of trades: USD โ†’ EUR โ†’ GBP โ†’ USD turns one dollar into the product of three rates. An arbitrage is a cycle whose product is greater than 1. Take logarithms and products become sums; use -log(rate) as the edge weight and "product greater than 1" becomes "sum less than 0", which is a negative cycle. Since any currency may be the start, set every distance to 0 at the beginning (equivalent to a hidden source connected to all vertices).

Python Arbitrage as a negative cycle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tolerance matters: floating-point rounding can fake tiny "improvements" around a cycle whose real product is exactly 1.

Common mistakes

  • Stopping after V - 2 or V passes without a check. Do V - 1 passes for the distances, then one extra pass for the cycle test.
  • Relaxing from an unreachable vertex. Always guard with dist[u] != INF.
  • Reusing updates inside a limited-pass variant. For "at most k edges", relax from a copy.
  • Trusting the distances after a negative cycle was found. Vertices reachable from the cycle have no meaningful shortest distance.
  • Using it where Dijkstra suffices. With non-negative weights Dijkstra is much faster.

When to use it

Choose Bellman-Ford when weights can be negative, when you must detect negative cycles, when the number of edges on the path is limited, or when the graph is small and the simple edge-list code is attractive. For all pairs at once, see Floyd-Warshall; for special graph shapes with faster options, see 0-1 BFS, A* and other shortest paths.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does Bellman-Ford need at most V - 1 passes when there is no negative cycle?

    After pass k all shortest paths with at most k edges are correct. A simple path has at most V - 1 edges, so V - 1 passes cover every shortest path.
  2. 2. What does it mean if an edge can still be relaxed in pass V?

    Without a negative cycle everything is stable after V - 1 passes. A further improvement means some cycle keeps lowering the cost.
  3. 3. What is the time complexity of Bellman-Ford with an edge list?

    Each of up to V - 1 passes scans all E edges, giving O(V * E).
  4. 4. In the cheapest-flights-with-k-stops problem, why do we relax from a copy of the distance list?

    Reading the copy means every update in pass i is built from paths of exactly i - 1 edges, so after k + 1 passes no route uses more than k + 1 flights.
  5. 5. How do you turn currency rates into a shortest-path problem?

    Products of rates become sums of logarithms. A product greater than 1 gives a negative sum of -log(rate), which is a negative cycle.

Summary

  • Bellman-Ford relaxes every edge, V - 1 times; after pass k all shortest paths of at most k edges are correct.
  • It handles negative edges and detects negative cycles with one extra pass.
  • Time is O(VยทE), space O(V); it works directly on an edge list.
  • Stop early when a pass changes nothing; follow parent to rebuild paths.
  • Limit passes to k + 1 (relaxing from a copy) to answer "at most k stops" questions.
  • Taking -log of rates turns arbitrage detection into negative cycle detection.
  • With only non-negative weights, Dijkstra is the faster choice.

Next: Floyd-Warshall