cf.completefrontend
GRAPHS · ADVANCED

Bellman-Ford

Find cheapest paths from one start even when some edges have negative costs, by relaxing every edge again and again, and detect loops that keep getting cheaper.

Time O(n * e)Space O(n)3 practice problemsStep-through picture

The idea

Dijkstra's algorithm breaks when some edges have negative costs, such as a refund or a discount. Bellman-Ford handles them. It is slower but much simpler: it goes over the whole list of edges several times, and each time it tries to improve every distance.

Trying to improve a distance with one edge is called relaxing it: if going to from and then along the edge is cheaper than the best known cost of to, update dist[to]. After one full pass over all edges, every cheapest path that uses at most 1 edge is correct. After two passes, every cheapest path with at most 2 edges is correct, and so on.

A cheapest path never needs to repeat a node, so it has at most n - 1 edges, and n - 1 passes are enough. If one more pass still improves something, the graph has a negative cycle: a loop whose total cost is below zero, which you could go around forever to make the cost as low as you like. Bellman-Ford reports that.

An everyday example

Word of mouth about cheap routes

Travelers share tips once a day: "I can get to town B for 4 coins." Each day, everyone hears every tip and updates their own best price. After one day you know every route that takes one hop; after two days, every route of two hops. With n towns, after n - 1 days nothing should change. If prices are still dropping, some loop of trips actually pays you money to ride it.

How the example maps to the code
In the exampleIn the code
One day of sharing tipsOne round over every edge
A traveler's best known pricedist[to]
Finding a cheaper route through a frienddist[from] + weight < dist[to]
A quiet day where nothing changeschanged stays false, so stop early
Prices still dropping after n - 1 daysA negative cycle

From the slow way to bellman-ford

  1. Dijkstra's algorithm locks in the closest node early, which is only safe when no edge is negative. A negative edge found later, like a refund, could make a locked node cheaper. The obvious fallback is to try every path, but the number of paths grows exponentially, so that's no good beyond tiny graphs.
  2. Notice that relaxing an edge is always safe: dist[to] = dist[from] + weight only ever stores the cost of a real path, and only when it's cheaper. So we can relax edges in any order, as many times as we like, and never make an answer wrong. The only question is how many times is enough.
  3. Count edges instead of costs. After one pass over every edge, every cheapest path that uses one edge is found. After a second pass, every cheapest path with two edges is found, because its last edge gets relaxed after the first part was already right. A cheapest path never repeats a node, so it has at most n - 1 edges, and n - 1 passes are enough, in any edge order.
  4. Two cheap extras finish it. If a pass changes nothing, the next pass would see the same numbers, so stop early. And if one more pass after n - 1 still lowers something, some cheapest path would need n edges, which means it repeats a node through a loop with a negative total. Passes over the edge list, an early stop, and a final check: that loop is Bellman-Ford.

How it works

  1. Set every dist to Infinity and dist[start] = 0.
  2. Repeat for round from 1 to n - 1.
  3. In each round, go through every edge [from, to, weight]. Skip it if from hasn't been reached yet.
  4. If dist[from] + weight is less than dist[to], update dist[to] and note that something changed.
  5. If a whole round changes nothing, every distance is final: stop early.
  6. Finally, check every edge once more. If any edge can still improve a distance, there is a negative cycle: return null. Otherwise return dist.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function bellmanFord(n, edges, start) {
  2. const dist = new Array(n).fill(Infinity);
  3. dist[start] = 0;
  4. for (let round = 1; round < n; round++) {
  5. let changed = false;
  6. for (const [from, to, weight] of edges) {
  7. if (dist[from] === Infinity) continue;
  8. if (dist[from] + weight < dist[to]) {
  9. dist[to] = dist[from] + weight;
  10. changed = true;
  11. }
  12. }
  13. if (!changed) break;
  14. }
  15. for (const [from, to, weight] of edges) {
  16. if (dist[from] !== Infinity && dist[from] + weight < dist[to]) return null;
  17. }
  18. return dist;
  19. }

How fast it is

TimeO(n * e)
Extra memoryO(n)

Up to n - 1 rounds each check all e edges. Only the dist array is stored, because it reads the edge list directly.

  • Best caseO(e)

    The edges are listed in the order paths use them, so round 1 finds every price and round 2 changes nothing: about 3e edge checks, including the final check.

  • Average caseO(k · e)

    k is the number of rounds that change something, at most the most edges on any cheapest path, plus one quiet round. It's often far below n on graphs with short cheapest paths.

  • Worst caseO(n · e)

    A long chain listed backwards, where each round fixes just one more node, or a graph with a negative loop, where all n - 1 rounds run and the final check fails.

Common mistakes

  • Running only until the first round with no change and skipping the extra negative-cycle check when the rounds ran out.
  • Relaxing edges that start from an unreached node. With negative weights, Infinity stays Infinity, but other sentinel values like 1e9 can drift and look reachable.
  • Using it for a "at most k edges" question without copying dist each round, which lets one round use several edges.
  • Using Bellman-Ford on large graphs with only positive costs. Dijkstra gives the same answer much faster.

When to use it

Look for these clues in a problem:

  • Some edge costs can be negative, such as refunds, credits, or gains.
  • The question asks whether a loop can make the total cost fall forever.
  • Paths are limited to at most k edges or k stops.
  • The graph is small enough that n * e steps is fine.

Check yourself

Answer each one in your head first, then open it.

Why are n - 1 rounds always enough when there's no negative loop?

Round k fixes every cheapest path with up to k edges, and a cheapest path never repeats a node, so it has at most n - 1 edges.

In the trace, why did it take three changing rounds instead of one?

The edges were listed backwards along the paths, so each round could only extend paths by about one edge. Listed in path order, round 1 alone finds every price.

Why can't it report a negative loop that the start can't reach?

Nodes on that loop keep dist of Infinity, and line 7 skips their edges. The loop never changes any price, so the final check never sees it.

What does the changed flag save?

Once a round changes nothing, every later round would too, so it can stop right away. On graphs with short cheapest paths, that turns n - 1 rounds into a few.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The first rule: every dist[v] is either Infinity or the cost of some real walk from the start to v. That's true at the start, and relaxing sets dist[to] to a walk to from plus one more edge. So dist is never lower than the true cheapest cost, as long as no negative loop exists.

The second rule: after round k, dist[v] is no more than the cheapest cost of any path to v with at most k edges. A path with k edges is a path with k - 1 edges to some u, then the edge u → v. After round k - 1, dist[u] is at most the first part's cost, and round k relaxes u → v, so dist[v] is at most the whole cost.

Without a negative loop, a cheapest path has at most n - 1 edges, so after round n - 1 both rules squeeze dist to the exact answer. A round that changes nothing proves the same thing early, because the next round would read the same values. With a negative loop v₁ → v₂ → ... → v₁ reachable from the start, suppose no edge could improve: then dist[vᵢ₊₁] <= dist[vᵢ] + weight for every edge of the loop. Adding these up around the loop cancels every dist and leaves 0 <= total weight, which contradicts a negative total. So some edge still improves, and the final check returns null.

Going deeper

3 more ideas

Why n - 1 rounds are enough

After round k, every node whose cheapest path uses at most k edges has its correct cost: the last edge of that path is relaxed in round k at the latest, after the node before it was already correct. Without negative cycles, a cheapest path never visits a node twice, so it has at most n - 1 edges. Round n - 1 therefore fixes everything.

Cost

Each round checks every edge, and there are at most n - 1 rounds plus one check, so the time is O(n * e). That's much slower than Dijkstra's O((n + e) log n) on big graphs, so use Bellman-Ford only when you need negative edges or an edge-count limit.

Limiting the number of edges

To find the cheapest path that uses at most k edges, run exactly k rounds, and in each round read distances from a copy of dist made at the start of the round. Without the copy, one round can chain several edges together and break the limit.

Work it by hand

Every step in a table, with why

Five nodes from start 0, with the edges listed in an unhelpful order and one negative edge, so prices keep falling for three rounds.

n = 5, edges = [[3,4,2], [1,3,4], [2,1,-6], [0,2,8], [0,1,3], [1,4,6]], start = 0

SteproundEdgedist[from] + weightdist afterWhat happensWhy
113→4, 1→3, 2→1dist[from] is ∞[0, ∞, ∞, ∞, ∞]Skip all threeNodes 3, 1, and 2 haven't been reached yet, so line 7 skips their edges.
210→2 (8)0 + 8 = 8[0, ∞, 8, ∞, ∞]ImproveThe start's edges are the first ones that can do anything.
310→1 (3)0 + 3 = 3[0, 3, 8, ∞, ∞]ImproveNode 1 gets the direct price 3.
411→4 (6)3 + 6 = 9[0, 3, 8, ∞, 9]Improve, changed = trueNode 1 was just reached in this same round, so its edge already helps.
523→4 (2)dist[3] is ∞[0, 3, 8, ∞, 9]SkipNode 3 still has no price at the start of round 2.
621→3 (4)3 + 4 = 7[0, 3, 8, 7, 9]ImproveNode 3 is reached for the first time, through node 1.
722→1 (-6)8 - 6 = 2[0, 2, 8, 7, 9]ImproveThe negative edge makes 0 → 2 → 1 cost 2, cheaper than the direct 3. Dijkstra would already have locked node 1 at 3.
820→2, 0→18 and 3[0, 2, 8, 7, 9]No change8 ties dist[2], and 3 is worse than the new 2.
921→4 (6)2 + 6 = 8[0, 2, 8, 7, 8]ImproveNode 1's cheaper price flows on to node 4.
1033→4 (2)7 + 2 = 9[0, 2, 8, 7, 8]No change9 is not less than 8. Node 3's price of 7 is about to drop anyway.
1131→3 (4)2 + 4 = 6[0, 2, 8, 6, 8]ImproveThe last change: node 3 is now reached through the cheap node 1. The rest of round 3 changes nothing.
124all 6 edgesnothing is cheaper[0, 2, 8, 6, 8]changed is false: breakA quiet round means every price is final. Round 4 is also the last allowed round, since n - 1 = 4.
13checkall 6 edgesnothing is cheaper[0, 2, 8, 6, 8]No negative loopThe extra pass on lines 15 and 16 finds no edge that still lowers a price.

It returns [0, 2, 8, 6, 8] after 4 rounds of 6 edge checks plus the final check of 6. With the same edges listed in path order, round 1 finds every price and round 2 is quiet, so only 2 rounds run.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bellman-FordO(n · e)O(n)Some edges are negative, you need to detect negative loops, or paths are limited to at most k edges.
Dijkstra's algorithmO(e log n)O(n + e)No edge is negative. It gives the same answer much faster on big graphs.
Floyd-WarshallO(n³)O(n²)You need every pair of nodes, not just one start, and the graph is small.

Extra memory: O(n): only the dist array. It reads the edge list directly and never builds adjacency lists.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bellman-Ford and the other approaches, on a scale where each line up is 10 times more steps.
  • Bellman-Ford O(n · e)
  • Dijkstra's algorithm O(e log n)
  • Floyd-Warshall O(n³)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bellman-Ford1001 million1 trillion
Dijkstra's algorithm339,96620 million
Floyd-Warshall1,0001 billionmore than a quadrillion

Inputs that need care

6 tricky inputs
A node that can't be reached from the start
Its dist stays Infinity, and line 7 skips its outgoing edges in every round.
A negative loop the start can't reach: [[0,1,1], [2,3,-2], [3,2,1]]
Nodes 2 and 3 stay Infinity and are skipped, so it returns [0, 1, Infinity, Infinity] without reporting the loop. To find any negative loop, start every dist at 0 instead.
A reachable negative loop: [[0,1,2], [1,2,3], [2,3,-1], [3,1,-3]]
The loop 1 → 2 → 3 → 1 totals -1, so prices fall every round, and the final check returns null.
An undirected graph with a negative edge
An undirected edge is two directed edges, so a negative one makes a loop a → b → a with a negative total. It returns null; negative undirected edges need a different model.
One node, n = 1
The round loop doesn't run at all, and it returns [0].
Using 1e9 instead of Infinity
An unreached node's edge could then turn 1e9 - 6 into a price that looks real. Keep Infinity, or keep the skip on line 7.

Variations and follow-ups

Twists interviewers add

Finding the negative loop itself

Keep prev[to] = from whenever a price drops. When the final check finds an edge that still improves, set that price and step back through prev n times: you're now surely on the loop. Keep stepping until you return to the same node to list it.

The queue version (SPFA)

Only nodes whose price changed can improve their neighbors, so keep those nodes in a queue and relax only their edges. It's often much faster on real graphs, but the worst case is still O(n · e).

Exchange rate loops

To check whether trading currencies in a loop makes money, use the weight -Math.log(rate) for each exchange. Multiplying rates becomes adding logarithms, and a loop that multiplies to more than 1 becomes a negative loop.

Systems of difference rules

Rules like x[j] - x[i] <= c become edges i → j with weight c. Add a start with 0-cost edges to every variable and run Bellman-Ford: the dist values satisfy every rule, and a negative loop means the rules can't all be true.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from negative costs (refunds, gains, credits), "detect a loop that makes the cost fall forever", or "at most k stops". Those three phrases rule out Dijkstra.
  • Explain the round count out loud: "after round k, every cheapest path with up to k edges is right, and a cheapest path has at most n - 1 edges". It justifies both the loop bound and the negative-loop check.
  • Test by hand a graph with the edges listed backwards, like the trace, and a three-node loop with a negative total. The first checks the number of rounds; the second checks the null return.
  • Expect "what's the cheapest flight with at most k stops?". Answer: run k + 1 rounds and, in each round, read prices from a copy of dist made before the round, so one round can't chain two edges.

Where frontend code uses it

The same idea in real UI code
  • Pricing and checkout flows that combine discounts and fees as edge costs, where some steps lower the total, need an algorithm that accepts negative values.
  • Currency or credit dashboards that check exchange rates for loops that turn a balance into more of itself, which is a negative-cycle check on the logarithms of the rates.
  • Some distance-vector network routing protocols, which route traffic between servers, are based on the same repeated relaxing idea.

Related algorithms