Bellman–Ford & Negative Edges

Some edges pay you back: a refund, a downhill stretch that recharges an electric car, a currency trade that gains money. Bellman–Ford handles negative weights and can even tell you when "keep going around" makes the cost fall forever.

advanced⏱ 12 min read

←Builds on

8Dijkstra's AlgorithmBellman–Ford keeps Dijkstra's relaxation but repeats it over every edge, so negative weights are fine.6Graph RepresentationsIt simply loops over the edge list V − 1 times.

Leads to→

10Floyd–Warshall: DP on GraphsLike Bellman–Ford it relaxes edges repeatedly and copes with negative weights.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Relax everything, again and again

Dijkstra fails with negative edges because it marks a vertex as final too early. Bellman–Ford drops the greedy marking altogether: it uses the same relaxation step, but applies it to every edge, in a fixed order, and repeats the whole sweep.

Why does that converge? Think about one shortest path s → a → b → c → d. The first sweep is guaranteed to relax s → a correctly; the second sweep then gets a → b right, the third b → c, and so on. After round k, every shortest path that uses at most k edges is correct, no matter in what order the edges are listed.

This is really dynamic programming over the number of edges, a preview of stage 10.

02V − 1 rounds are enough

Without negative cycles a shortest path never repeats a vertex, so it has at most V − 1 edges. Hence V − 1 rounds always suffice:

d[s] = 0; repeat V−1 times: for each edge (u, v, w): if d[u] + w < d[v]: d[v] = d[u] + w

The table shows the visualizer's 5-vertex graph. Round 1 reaches everyone; round 2 finds the cheaper way to vertex 2 through the −2 edge; round 3 pushes that improvement on to vertex 5 (−2). Round 4 changes nothing.

That gives a free speedup: if a whole round changes nothing, stop. Nothing can change later either. On many real inputs this ends far before V − 1 rounds.

Highlighted cells changed in that round.

03Negative cycles: one extra round

If a cycle has negative total weight, you can go around it as often as you like and make the "distance" as small as you want: no shortest path exists.

Bellman–Ford detects this for free. After V − 1 rounds all real shortest paths are final, so run one more round. If any edge still relaxes, the only explanation is a negative cycle reachable from the source.

In the visualizer, set the weight of edge 4→3 to −7: the cycle 3 → 2 → 4 → 3 then weighs −2 + 8 − 7 = −1, and the extra round reports it. The classic real use is currency arbitrage: with weights −log(rate), a negative cycle is a chain of trades that ends with more money than it started.

04Cost, and choosing the right tool

Each round touches all E edges, and there are up to V − 1 rounds plus the check: O(V·E) time and only O(V) extra memory (just d[] and p[], the edges can stay in a plain list). That is much slower than Dijkstra's O((V + E) log V), so use it only when you need what it offers:

negative edge weights;
detecting negative cycles;
"at most k edges" questions (stop after k rounds, copying d[] each round).

A variant built on a queue (often called SPFA) relaxes again only the edges out of vertices that just improved. It is often fast in practice but has the same worst case.

Cost at a glance

TimeO(V·E)

Negative cycle checkO(E)

Extra memoryO(V)

Remember

Bellman–Ford relaxes every edge V − 1 times; after round k all shortest paths with ≤ k edges are correct.
If an extra round still improves something, a negative cycle is reachable and no shortest path exists.
It costs O(V·E), so prefer Dijkstra whenever all weights are non-negative.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Count the improvements per round: they shrink to zero. Then set 4→3 to −7 and watch the extra round catch the negative cycle.

Interactive visualizerfocus here, then space ← →

Directed weighted graph (source: 1) · round 0

v	1	2	3	4	5
dist	0	∞	∞	∞	∞
parent	nil	nil	nil	nil	nil

Bellman–Ford finds shortest paths even with NEGATIVE edges, where Dijkstra’s greedy marking would break. dist[1] = 0, all others ∞.

Pseudocode

 1 dist[s]=0, others ∞ 2 repeat |V|-1 times: 3   for every edge (u→v,w): if dist[u]+w < dist[v], relax it 4 one more pass: any relaxation now ⇒ a negative cycle

1 / 1

Check

Three questions. Pick an answer to see why.

A graph has 6 vertices and no negative cycles. How many rounds can Bellman–Ford need at most before distances are final?

Round 3 finished and changed nothing. What do you know?

You need cheapest flights using at most k flights. Which tool fits best?

Practice

Real problems to lock it in, easiest first.

LeetCodeNetwork Delay Time intermediate↗LeetCodeCheapest Flights Within K Stops intermediate↗CSESHigh Score advanced↗CSESCycle Finding advanced↗