Skip to content

level 7 · Graphs

Bellman–Ford

Slower than Dijkstra, and it can do the one thing Dijkstra can't.

13 min 105 XP

what is it

Start here

Dijkstra rests on one assumption: that once a node is the nearest unfinished one, nothing can ever reach it more cheaply. It's a lovely argument, and it has a hole. It assumes travelling further can never make things cheaper — which is only true when every edge costs something positive.

Now put a **negative** edge on the map. Suddenly a longer detour really can come out cheaper. Dijkstra finalises a node early, moves on, and never looks back — and it is confidently, silently wrong.

Bellman–Ford makes no assumption at all. It is, frankly, stupider: it just relaxes **every** edge, over and over, n−1 times. No greedy choice, no priority queue, no cleverness. And because it never commits to anything, negative edges don't trouble it in the slightest.

Why n−1 rounds? Because a shortest path can't contain more than n−1 edges (any more would mean revisiting a node), and each round is guaranteed to lock in at least one more edge of every shortest path. After n−1 rounds, everything has settled.

And then it does something Dijkstra cannot do at all. It runs **one more round**. If anything *still* gets cheaper — after everything should already be final — then there must be a loop you can ride round forever, getting cheaper each lap. A negative cycle. 'Shortest path' has no answer, and Bellman–Ford is the algorithm that can tell you so rather than looping forever.

real-life analogy

Picture it

A currency exchange with an arbitrage loop

Trade dollars → euros → yen → dollars and come out with more money than you started with. Now 'the cheapest sequence of trades' is meaningless — just go round the loop forever. Detecting that impossible loop is more valuable than any route, and it's exactly what the extra round finds.

interactive visualization

Watch it run

The pink edge C→B costs −4. Watch a negative edge make a longer route cheaper.

63-4283
A 0
B ∞
C ∞
D ∞
E ∞

Look at the pink edge: C → B costs **−4**. Dijkstra would go badly wrong here — it finalises B early on the cheap-looking direct route and never reconsiders. Bellman–Ford makes no assumptions at all, so it copes.

step 01/17

  • just discovered
  • visited
  • found it
  • visiting now
  • waiting in the queue / stack
1function bellmanFord(nodes, edges, start) {
2 const dist = {};
3 for (const v of nodes) dist[v] = Infinity;
4 dist[start] = 0;
5
6 // Relax EVERY edge, n-1 times. No cleverness at all.
7 for (let round = 1; round < nodes.length; round++) {
8 for (const [u, v, w] of edges) {
9 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
10 }
11 }
12
13 // One more round. If anything still improves, a negative
14 // cycle exists — and "shortest" has no meaning.
15 for (const [u, v, w] of edges) {
16 if (dist[u] + w < dist[v]) return null; // negative cycle
17 }
18
19 return dist;
20}

variables right now

start
A
negativeEdge
C → B = −4
comparisons 0moves 0

the dry run · every step, in words

17 steps

complexity

What it costs

best case
O(E)
average
O(V × E)
worst case
O(V × E)
extra memory
O(V)

V−1 rounds, each sweeping all E edges: O(V × E). That's markedly slower than Dijkstra's O(E log V). You pay that price for two things Dijkstra cannot give you: negative edges, and negative-cycle detection.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²) · this one
input size →work →

common mistakes

Common traps

  • Reaching for Dijkstra on a graph with negative edges.

    It returns a wrong answer without any error — the worst failure mode there is. Negative weights mean Bellman–Ford.

  • Skipping the final extra round.

    That round is the negative-cycle detector, and it's half the reason to use this algorithm. Without it you'll happily report distances that don't exist.

  • Running only a few rounds because 'it looks settled'.

    You need V−1 rounds in the worst case. Do add the early exit — if a whole round changes nothing, stop — but don't guess a smaller number.

  • Thinking a negative cycle just means 'a very cheap route'.

    It means there is *no* shortest path. You could loop forever, getting cheaper each time. The right answer is 'this question has no answer'.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+105 XP

01Why does Dijkstra fail on negative edges?

02How does Bellman–Ford detect a negative cycle?

03What do you give up by using Bellman–Ford instead of Dijkstra?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.