Graph AlgosAlgorithmaka SSSP with negative edges, Bellman-Ford-Moore

Bellman-Ford

Single-source shortest paths that tolerate negative edge weights: relax every edge V - 1 times, then one more pass to detect negative cycles.

▶ VisualizePattern: Shortest Path (Weighted)Practice (2)
Progress

Overview

Bellman-Ford solves single-source shortest paths on graphs where edges may be negative. It has no clever ordering: it simply relaxes every edge, repeats that V - 1 times, and is guaranteed correct because after i rounds every shortest path that uses at most i edges has been found. A V-th round that still improves something proves a negative cycle reachable from the source.

Preconditions and complexity: directed graph (an undirected negative edge is itself a negative cycle), any weights, single source. Time O(V · E) — on a dense graph that is O(V³), and even on sparse graphs it is far slower than Dijkstra's Algorithm's O((V + E) log V). Use it only when negative edges exist, when you must detect negative cycles, or when a bound on path length (at most k edges) is part of the problem.

shortest pathnegative edgesnegative cyclerelaxationO(VE)

Intuition

A mental model before the formal terms.

Think of dist as a rumour spreading one hop per round. In round 1 everyone adjacent to the source learns the best one-edge price. In round 2 everyone learns the best price using two edges, because their neighbours now hold correct one-edge prices. A shortest path never revisits a node (if there is no negative cycle), so it has at most V - 1 edges, and after V - 1 rounds the rumour has stabilised. If prices still drop in round V, someone is looping around a cycle that pays you to travel it — a negative cycle.

How it works

  1. Set dist[s] = 0, all others ∞. Represent the graph as an Edge List (u, v, w).
  2. Repeat V - 1 times: for every edge (u, v, w), if dist[u] + w < dist[v] set dist[v] = dist[u] + w, parent[v] = u. Skip edges whose dist[u] is still ∞.
  3. Early exit: if a full round changes nothing, distances are final — stop.
  4. Negative-cycle check: run one more round. Any edge that still relaxes lies on, or is reachable from, a negative cycle. To extract the cycle, follow parent from that v for V steps to land inside the cycle, then walk around it.
  5. Variant: to find shortest paths with at most k edges, run exactly k rounds but relax from a copy of the previous round's distances so that one round cannot chain several edges.

Why it works

Induction on rounds: after round i, dist[v] ≤ the weight of the best path to v with at most i edges. Base: round 0, only s at 0. Step: the best (i+1)-edge path ends with some edge (u, v); its prefix is an i-edge path to u, already reflected in dist[u], so relaxing (u, v) in round i+1 sets dist[v] at least as low.

Without a negative cycle, some shortest path is simple and has ≤ V - 1 edges, so V - 1 rounds suffice. dist never goes below the true shortest distance because every update corresponds to an actual walk.

If a negative cycle is reachable, no finite shortest distance exists for its nodes, so relaxation continues forever; in particular round V still improves something. Conversely if round V improves nothing, the values are a fixed point satisfying the triangle inequality, hence optimal.

Recognition

How to tell a problem wants this.

  • Edge weights can be negative (costs with refunds, currency exchange as -log rate, "profit" edges).
  • The problem asks to detect a negative cycle or an arbitrage opportunity.
  • "At most k stops / edges" constraints — the round-limited variant is the natural fit.
  • Small graphs (V·E ≤ ~10^7) where simplicity matters more than speed.
“weighted graph” → Shortest Path (Weighted)“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

4568-3921S0A∞B∞C∞D∞E∞
Distances per round
roundSABCDE
00∞∞∞∞∞
now0∞∞∞∞∞
1/21dist[S] = 0, all others ∞. Bellman-Ford relaxes every edge up to n-1 = 5 times: after round i every shortest path using ≤ i edges is correct, so 5 rounds cover any simple path.
Edge being checkedEdge that improved a distance this roundCurrent parent edgeFinal shortest pathEdge proving a negative cycle
PseudocodeLearn Bellman-Ford →
1dist = {v: ∞}; dist[source] = 0
2for round in 1 .. n-1:
3  for (u, v, w) in edges:
4    if dist[u] + w < dist[v]:
5      dist[v] = dist[u] + w; parent[v] = u
6  if nothing changed: break
7for (u, v, w) in edges:
8  if dist[u] + w < dist[v]: report negative cycle
Complexity
best O(E)
avg O(V · E)
worst O(V · E)
space O(V)
Speed

Pseudocode

1dist = [INF] * n; dist[s] = 0
2for round in 1..n-1:
3  changed = false
4  for (u, v, w) in edges:
5    if dist[u] != INF and dist[u] + w < dist[v]:
6      dist[v] = dist[u] + w; parent[v] = u; changed = true
7  if not changed: break
8for (u, v, w) in edges: if dist[u] + w < dist[v]: report negative cycle

Implementations

1from math import inf
2 
3 
4def bellman_ford(
5    n: int, edges: list[tuple[int, int, int]], s: int
6) -> tuple[list[float], list[int], bool]:
7    """edges = directed (u, v, w) triples; nodes 0..n-1.
8    Returns (dist, parent, has_negative_cycle); dist = inf for unreachable nodes."""
91 · Initialize distances
10    dist: list[float] = [inf] * n
11    parent = [-1] * n
12    dist[s] = 0
132 · Relax every edge V - 1 times
14    for _ in range(n - 1):
15        changed = False
16        for u, v, w in edges:
17            if dist[u] != inf and dist[u] + w < dist[v]:
18                dist[v] = dist[u] + w
19                parent[v] = u
20                changed = True
213 · Early exit when a round changes nothing
22        if not changed:
23            break
244 · Negative-cycle detection round
25    has_negative_cycle = any(
26        dist[u] != inf and dist[u] + w < dist[v] for u, v, w in edges
27    )
285 · Result
29    return dist, parent, has_negative_cycle
Walkthrough
  1. Edges are (u, v, w) tuples unpacked directly in the for header.
  2. math.inf is the idiomatic sentinel; inf + w stays inf, so the guard mainly saves work and keeps parity with C++.
  3. The early exit uses a changed flag; for ... else could detect it too but the flag is clearer.
  4. The detection round is a generator expression inside any(...) — it short-circuits on the first still-relaxing edge.
Complexity (this implementation)
time O(V · E) · space O(V)

CPython interprets ~10^7 relaxations per second; V·E above ~10^7 needs PyPy or a rethink.

Language notes
  • dist is list[float] because inf is a float; mixing ints and floats compares correctly in Python.
  • The any(...) generator allocates no intermediate list — preferred over a list comprehension here.
  • For the "at most k edges" variant, relax from a copy: nxt = dist[:] each round.
Common mistakes in this language
  • Using sys.maxsize as infinity and then treating sys.maxsize + w as unreachable — it is a perfectly finite int; use math.inf.
  • Relaxing in place for the k-edges variant, letting one round chain multiple edges.
  • Writing for u, v, w in edges: when edges are lists of lists of varying length — unpacking raises ValueError mid-run.
Language differences that matter here
  • Infinity sentinel: JS/TS Infinity and Python math.inf absorb additions safely (inf + w == inf), so the dist[u] != INF guard is an optimisation there; in C++ INF + w on long long is undefined behaviour, so the guard is mandatory (or shrink INF to MAX/4).
  • Edge shape: C++ uses a small struct Edge; JS/TS destructure [u, v, w] tuples (TS checks the arity); Python unpacks (u, v, w) tuples in the loop header.
  • Detection round: JS/TS edges.some(...) and Python any(generator) both short-circuit; C++ uses a plain loop with early return false.
  • Number range: Python ints are unbounded; C++ needs long long; JS/TS integer sums are exact only below 2^53.

Complexity

Best
O(E)
Average
O(V · E)
Worst
O(V · E)
Space
O(V)

Best case: distances converge after one round and the early exit fires. SPFA (queue-based Bellman-Ford) is often fast in practice but still O(VE) worst case.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Negative edge weights without negative cycles (Dijkstra is wrong here).
  • Detecting negative cycles: arbitrage, "can the cost be decreased forever?".
  • Shortest path with a bound on the number of edges (k rounds with a copied array).
  • As the reweighting step of Johnson's all-pairs algorithm on sparse graphs with negative edges.
  • Distributed settings (distance-vector routing) where each node only talks to neighbours.
Avoid it when
  • All weights non-negative — Dijkstra's Algorithm is asymptotically and practically much faster.
  • Unweighted — BFS Shortest Path (Unweighted).
  • All-pairs on a small dense graph — Floyd-Warshall is O(V³) versus O(V² · E) ≈ O(V⁴) for running Bellman-Ford from every node.
  • Large sparse graphs (V, E ≈ 10^5) without negative edges — O(VE) = 10^10 is infeasible.

Alternatives

Dijkstra's AlgorithmFloyd-WarshallBFS Shortest Path (Unweighted)
Compare: Dijkstra vs Bellman-Ford

Common mistakes

  • Relaxing edges out of nodes with dist = ∞ — with fixed-width integers ∞ + w overflows (or, for negative w, becomes a bogus finite value).
  • For the "at most k edges" variant, relaxing in place: one round can then chain many edges and exceeds the limit. Relax from a copy.
  • Concluding "negative cycle" from the check without restricting to nodes reachable from the source — unreachable cycles are irrelevant if only s-distances matter (the check above already skips ∞ tails).
  • Running exactly V rounds and treating the last as normal — the V-th round is the detection round.
  • Applying it to an undirected graph with a negative edge: that edge alone is a negative cycle.

Interview patterns

  • Cheapest flights within k stops: k + 1 rounds with a copied distance array.
  • Currency arbitrage: edge weight -log(rate), negative cycle ⇔ arbitrage.
  • Detect and print a negative cycle by following parents V times from a still-relaxing node.
  • Johnson's algorithm: Bellman-Ford from a virtual source to compute potentials, then Dijkstra from every node.
Interview questions on this
Mock interviews

Example problems

Network Delay TimemediumCheapest Flights Within K Stopsmedium