Bellman-Ford Algorithm: Shortest Paths With Negative Weights
Bellman-Ford finds shortest paths from a source with negative edges and detects negative cycles. Intuition, JavaScript code, a walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Dijkstra's algorithm is fast, but it makes one assumption that quietly breaks the moment a graph has a negative edge: once a node is finalized, its distance never improves. Add an edge with weight -3 and that promise falls apart — a cheaper route can appear after you've already locked a node in.
Bellman-Ford throws out the greedy shortcut. Instead of committing to nodes one at a time, it relaxes every edge, repeatedly, letting better distances ripple outward pass by pass. It's slower than Dijkstra, but it earns two things Dijkstra can't offer: correct answers with negative weights, and the ability to detect a negative cycle — a loop you could ride forever to make paths infinitely cheap.
This guide follows the exact algorithm in the Bellman Ford Algorithm visualizer, including its edge ordering and early-stop check.
The problem
Given a directed graph with V nodes and a list of weighted edges [u, v, w] (an edge from u to v with weight w, possibly negative), compute the shortest distance from a source node to every other node. If the graph contains a negative-weight cycle reachable from the source, report that no shortest paths exist.
Input: V = 4, src = 0
edges = [ [0,1,4], [0,2,5], [1,3,5], [2,1,-3] ]
Output: dist = [0, 2, 5, 7]
// dist[1] = 2, not 4: the route 0 → 2 → 1 costs 5 + (-3) = 2,
// which beats the direct edge 0 → 1 of weight 4.That single negative edge is the whole story. A greedy algorithm would fix dist[1] = 4 early and move on. Bellman-Ford keeps the door open, so the -3 shortcut gets a chance to overwrite it later.
The brute force baseline
The literal definition of "shortest path" suggests enumerating every path from the source to each node and keeping the cheapest.
function shortestByEnumeration(edges, V, src, target) {
let best = Infinity;
function dfs(node, cost, visited) {
if (node === target) { best = Math.min(best, cost); return; }
for (const [u, v, w] of edges) {
if (u === node && !visited.has(v)) {
visited.add(v);
dfs(v, cost + w, visited);
visited.delete(v);
}
}
}
dfs(src, 0, new Set([src]));
return best;
}This is correct but catastrophic. The number of simple paths in a dense graph grows factorially, so enumeration is exponential. Worse, without the visited guard it would loop forever the instant a cycle appears — and you'd have no way to tell a helpful cycle from a negative one. The enumeration also throws away work: the shortest path to a far node reuses the shortest path to its predecessor, but this DFS recomputes prefixes from scratch every time.
The key insight: a shortest path has at most V-1 edges
Here's the fact that tames the explosion. If a graph has V nodes and no negative cycle, then any shortest path visits each node at most once — so it uses at most V - 1 edges. Any path longer than that must repeat a node, forming a cycle you'd only include if it made the path cheaper, which a non-negative-cycle graph never does.
That bound turns an infinite search into a fixed number of sweeps. Define relaxing an edge u → v with weight w as:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wEach full pass over all edges lets shortest-path information travel one more hop. After pass 1, every correct distance reachable in 1 edge is set. After pass 2, every distance reachable in 2 edges. So V - 1 passes are enough to settle every shortest path — regardless of the order edges are listed in.
And the detection trick falls out for free: run one more pass after the V - 1. If any edge can still be relaxed, some path is getting cheaper past the V - 1 limit — which is only possible if a negative cycle exists.
The optimal solution
This mirrors the CODE_LINES in the visualizer's source (components/visualize/graphs/bellman-ford.tsx): V - 1 relaxation passes with an early-stop flag, then a final verification pass for negative cycles.
function bellmanFord(edges, V, src) {
const dist = new Array(V).fill(Infinity);
dist[src] = 0;
// Relax all edges V-1 times
for (let i = 0; i < V - 1; i++) {
let updated = false;
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
updated = true;
}
}
// Early stopping: a pass with no relaxation means we've converged
if (!updated) break;
}
// One extra pass: any relaxable edge now means a negative cycle
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
console.log("Negative Weight cycle Detected");
return null;
}
}
return dist;
}Two guards carry real weight. The dist[u] !== Infinity check prevents Infinity + w from producing a bogus finite-looking comparison and stops unreachable nodes from poisoning their neighbors. The updated flag is a genuine speedup: if an entire pass changes nothing, no later pass can either, so the loop breaks early instead of grinding through all V - 1 iterations.
Walkthrough
Trace V = 4, src = 0, with edges in the exact listed order [0,1,4], [0,2,5], [1,3,5], [2,1,-3]. Start state: dist = [0, ∞, ∞, ∞].
| Pass | Edge (u→v, w) | dist[u] + w | vs dist[v] | Action | dist after |
|---|---|---|---|---|---|
| 1 | 0→1 (4) | 0 + 4 = 4 | < ∞ | relax | [0, 4, ∞, ∞] |
| 1 | 0→2 (5) | 0 + 5 = 5 | < ∞ | relax | [0, 4, 5, ∞] |
| 1 | 1→3 (5) | 4 + 5 = 9 | < ∞ | relax | [0, 4, 5, 9] |
| 1 | 2→1 (-3) | 5 + (-3) = 2 | < 4 | relax | [0, 2, 5, 9] |
| 2 | 0→1 (4) | 0 + 4 = 4 | not < 2 | ignore | [0, 2, 5, 9] |
| 2 | 0→2 (5) | 0 + 5 = 5 | not < 5 | ignore | [0, 2, 5, 9] |
| 2 | 1→3 (5) | 2 + 5 = 7 | < 9 | relax | [0, 2, 5, 7] |
| 2 | 2→1 (-3) | 5 + (-3) = 2 | not < 2 | ignore | [0, 2, 5, 7] |
| 3 | all edges | — | — | no relaxation → updated = false, break | [0, 2, 5, 7] |
Pass 1 sets dist[1] = 4 from the direct edge, then the last edge of the same pass discovers the -3 shortcut and rewrites it to 2. But that improvement arrived too late to help node 3 in pass 1 — dist[3] was already fixed at 9 using the stale dist[1] = 4. That's exactly why a second pass exists: pass 2 revisits 1→3 with the fresher dist[1] = 2 and drops dist[3] to 7. Pass 3 changes nothing, so the early-stop flag fires and the loop breaks before its final iteration. The verification pass finds no relaxable edge, so [0, 2, 5, 7] is final.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Path enumeration | O(V!) | O(V) | factorially many simple paths to search |
| Dijkstra (binary heap) | O(E log V) | O(V) | faster, but wrong with negative edges |
| Bellman-Ford | O(V · E) | O(V) | up to V−1 passes, each scanning all E edges |
Each pass touches every edge once for O(E) work, and there are at most V - 1 passes, giving O(V · E). Space is O(V) for the distance array. The early-stop flag can cut passes dramatically on graphs that converge quickly — the walkthrough settled in 2 real passes instead of 3 — but the worst case stays O(V · E) when edge ordering forces information to crawl one hop per pass.
Common mistakes
- Skipping the
dist[u] === Infinityguard. In JavaScriptInfinity + (-3)is stillInfinity, so a naive comparison won't crash — but in languages that use a large integer sentinel,INT_MAX + woverflows to a negative number and falsely "relaxes" through unreachable nodes. - Running only
V - 1passes and declaring victory. Without the extra verification pass you silently return garbage distances on a graph that actually has a negative cycle. Detection is the algorithm's headline feature. - Confusing "reachable" with "has a negative cycle." Bellman-Ford only reports cycles reachable from the source. A negative cycle sitting in a disconnected component never gets relaxed and is correctly ignored.
- Reaching for Dijkstra because it's faster. Dijkstra's greedy finalization assumes no future edge can lower a settled node. One negative edge violates that, and it returns confidently wrong answers.
- Breaking early on the wrong condition. The
updatedflag must reset tofalseat the start of each pass. Reset it once before the loop and it stays true forever, killing the optimization.
Where this pattern shows up next
Bellman-Ford is the entry point to weighted-graph traversal. These build on the same graph-modeling muscles:
- Find if Path Exists in Graph — reachability without weights, the simplest version of "can I get from A to B?"
- All Paths From Source to Target — full path enumeration on a DAG, the brute-force cousin of shortest-path search.
- Clone Graph — traversal plus bookkeeping, where a visited map replaces the distance array.
- Max Area of Island — grid-as-graph flood fill, relaxation's spatial sibling.
You can also step through Bellman-Ford interactively to watch each edge relax and the distance array settle pass by pass.
FAQ
Why does Bellman-Ford need V-1 passes?
Because a shortest path in a graph without negative cycles uses at most V - 1 edges — any longer path would repeat a node. Each relaxation pass lets shortest-path information advance exactly one more edge from the source, so after V - 1 passes every reachable node has its final distance, no matter what order the edges are stored in. A pass that changes nothing means everything has already converged, which is why the early-stop flag can finish sooner.
How does Bellman-Ford detect a negative cycle?
After the V - 1 relaxation passes, it runs one additional pass over all edges. If any edge can still be relaxed — meaning some dist[u] + w < dist[v] remains true — then a path is still getting cheaper beyond the V - 1-edge limit. That's only possible when a negative-weight cycle is reachable from the source, so the algorithm reports it and returns null instead of nonsensical, ever-shrinking distances.
When should I use Bellman-Ford instead of Dijkstra?
Use Bellman-Ford when edges can be negative, or when you specifically need to detect negative cycles. Dijkstra is faster at O(E log V) but assumes that once a node's distance is finalized, no cheaper route exists — an assumption a negative edge breaks, causing wrong answers. If every weight is non-negative and you only need distances, prefer Dijkstra; reach for Bellman-Ford the moment negatives enter the picture.
What does Bellman-Ford return for an unreachable node?
Its distance stays Infinity. The source is seeded with dist[src] = 0, and relaxation only propagates from nodes that already have a finite distance. A node with no path from the source is never on the receiving end of a successful relaxation, so it keeps its initial Infinity — which is the correct, meaningful answer for "no path exists."
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.