The Bellman-Ford algorithm finds the shortest paths from one node to every other node in a weighted, directed graph, even when some edges are negative. It relaxes every edge V−1 times, then makes one more pass: if any distance can still shrink, the graph has a negative cycle and no shortest path exists. It runs in O(V·E) time, slower than Dijkstra's algorithm, which is why you use it only when negative weights are possible.
Tested with: Node.js 20.20 and Python 3.14, October 2026. The JavaScript version was cross-checked against Floyd-Warshall on 300 random graphs, and every distance below comes from running the code.
How Bellman-Ford Works
- Start: distance 0 for the source, Infinity for everything else.
- Relax every edge: for each edge u → v with weight w, if dist[u] + w < dist[v], update dist[v] and remember u as v's previous node.
- Repeat V−1 times. A shortest path without cycles uses at most V−1 edges, and each pass fixes at least one more edge of every shortest path.
- Check once more. If any edge can still be relaxed, there's a negative cycle reachable from the source.
- Stop early when a whole pass changes nothing; the remaining passes would change nothing either.
Walkthrough: Pass by Pass
Five nodes, eight edges, two of them negative, starting at A:
A → B 6 C → D -3
A → C 7 C → E 9
B → D 5 D → B -2
B → E -4 E → D 7Distances after each pass, relaxing edges in the order listed (A→B, A→C, B→D, B→E, C→D, C→E, D→B, E→D):
| After | A | B | C | D | E |
|---|---|---|---|---|---|
| Start | 0 | ∞ | ∞ | ∞ | ∞ |
| Pass 1 | 0 | 2 | 7 | 4 | 2 |
| Pass 2 | 0 | 2 | 7 | 4 | -2 |
| Pass 3 | 0 | 2 | 7 | 4 | -2 (no change: stop) |
- In pass 1, A→C makes C = 7, C→D makes D = 4, and D→B (−2) then lowers B from 6 to 2, all in the same pass because the edges happen to be in a helpful order.
- B→E ran before B dropped to 2, so E only reached its final value, 2 + (−4) = −2, in pass 2.
- Pass 3 changed nothing, so the algorithm stopped after 3 of the possible 4 passes.
Final shortest path to E: A → C → D → B → E, cost 7 − 3 − 2 − 4 = −2. With a different edge order you'd need more passes, but never more than V−1.
Bellman-Ford in JavaScript
// Shortest paths from `source` in a directed graph whose edges may be negative.
// edges: [from, to, weight][]. Returns distances, the previous node on each
// shortest path, and a negative cycle (as a list of nodes) if one is reachable.
export function bellmanFord(nodes, edges, source) {
const dist = new Map(nodes.map((n) => [n, Infinity]));
const prev = new Map();
dist.set(source, 0);
// A shortest path has at most V-1 edges, so V-1 passes are enough
for (let pass = 1; pass < nodes.length; pass++) {
let changed = false;
for (const [u, v, w] of edges) {
if (dist.get(u) + w < dist.get(v)) {
dist.set(v, dist.get(u) + w);
prev.set(v, u);
changed = true;
}
}
if (!changed) break; // nothing improved: we're done early
}
// One more pass: if anything still improves, there's a negative cycle
for (const [u, v, w] of edges) {
if (dist.get(u) + w < dist.get(v)) {
prev.set(v, u);
return { dist, prev, negativeCycle: findCycle(prev, v, nodes.length) };
}
}
return { dist, prev, negativeCycle: null };
}
function findCycle(prev, start, size) {
let node = start;
for (let i = 0; i < size; i++) node = prev.get(node); // step back into the cycle
const cycle = [node];
for (let at = prev.get(node); at !== node; at = prev.get(at)) cycle.push(at);
return cycle.reverse();
}
// Rebuild the path to `target` from the prev map
export function pathTo(prev, source, target) {
const path = [target];
while (path[0] !== source) {
const before = prev.get(path[0]);
if (before === undefined) return null; // unreachable
path.unshift(before);
}
return path;
}import { bellmanFord, pathTo } from "./bellman-ford.js";
const nodes = ["A", "B", "C", "D", "E"];
const edges = [
["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],
["C", "D", -3], ["C", "E", 9], ["D", "B", -2], ["E", "D", 7],
];
const { dist, prev, negativeCycle } = bellmanFord(nodes, edges, "A");
dist; // Map { A → 0, B → 2, C → 7, D → 4, E → -2 }
pathTo(prev, "A", "E"); // ["A", "C", "D", "B", "E"]
negativeCycle; // null- prev stores where each shortest path came from, so pathTo can rebuild the route. An unreachable node keeps distance Infinity and pathTo returns null.
- When a negative cycle is found, findCycle walks back V steps through prev (which guarantees it lands inside the cycle) and returns the nodes of the cycle.
- Comparisons with Infinity are safe in JavaScript: Infinity + (-7) is still Infinity, so unreachable nodes never "improve" others.
Bellman-Ford in Python
import math
def bellman_ford(nodes, edges, source):
dist = {n: math.inf for n in nodes}
prev = {}
dist[source] = 0
for _ in range(len(nodes) - 1):
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
changed = True
if not changed:
break
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("Graph contains a negative cycle")
return dist, prev
nodes = ["A", "B", "C", "D"]
edges = [("A", "B", 2), ("A", "C", 5), ("C", "B", -4), ("B", "D", 1)]
print(bellman_ford(nodes, edges, "A")[0]) # {'A': 0, 'B': 1, 'C': 5, 'D': 2}This version raises ValueError on a negative cycle instead of returning it. It printed the distances shown in the comment.
Negative Cycles
// The example graph from an older version of this article
const edges = [
["A", "B", 4], ["A", "C", 2], ["B", "C", 3],
["B", "D", 2], ["C", "D", 5], ["D", "B", -7],
];
bellmanFord(["A", "B", "C", "D"], edges, "A").negativeCycle; // ["B", "D"]
// B → D → B costs 2 + (-7) = -5, so going around again is always "shorter".
// Without the extra check, the old code returned [0, -11, -3, -4]: meaningless numbers, no warning.A negative cycle has no shortest path: every extra lap lowers the cost. That's why the final check matters, and why an implementation that skips it returns plausible-looking but wrong numbers.
- In an undirected graph, one negative edge is already a negative cycle (A → B → A). In our test a single −1 edge stored both ways was reported as the cycle [A, B]. Bellman-Ford is really a directed-graph algorithm.
- The check only finds cycles reachable from the source. To check a whole graph, add a virtual source with 0-weight edges to every node.
Real Example: Detecting Currency Arbitrage
import { bellmanFord } from "./bellman-ford.js";
// Currency arbitrage: converting around a loop and ending up with more money.
// Multiplying rates becomes adding logs, and "more than 1" becomes a
// negative cycle when each edge weight is -log(rate).
const rates = {
USD: { EUR: 0.92, GBP: 0.79 },
EUR: { GBP: 0.86, USD: 1.09 },
GBP: { USD: 1.28, EUR: 1.17 },
};
const nodes = Object.keys(rates);
const edges = nodes.flatMap((from) =>
Object.entries(rates[from]).map(([to, rate]) => [from, to, -Math.log(rate)])
);
const { negativeCycle } = bellmanFord(nodes, edges, "USD");
if (negativeCycle) {
const loop = [...negativeCycle, negativeCycle[0]];
let amount = 1;
for (let i = 0; i < loop.length - 1; i++) amount *= rates[loop[i]][loop[i + 1]];
console.log(`Arbitrage: ${loop.join(" → ")} turns 1 into ${amount.toFixed(4)}`);
} else {
console.log("No arbitrage");
}With these made-up rates it printed: Arbitrage: GBP → USD → EUR → GBP turns 1 into 1.0127. Converting around the loop multiplies the rates (1.28 × 0.92 × 0.86 ≈ 1.0127). Taking −log of each rate turns "product greater than 1" into "sum less than 0", which is exactly a negative cycle.
Bellman-Ford vs Dijkstra
// A → B 2, A → C 5, C → B -4, B → D 1
// Dijkstra: B = 2, D = 3 (B was "finished" before C → B was seen)
// Bellman-Ford: B = 1, D = 2 via A → C → B → DWe ran both on that graph: Dijkstra finalized B at 2 before it ever looked at the −4 edge, so B and D were wrong. Bellman-Ford got B = 1 and D = 2.
| Bellman-Ford | Dijkstra | |
|---|---|---|
| Negative edges | Yes | No (can give wrong answers) |
| Detects negative cycles | Yes | No |
| Time | O(V·E) | O((V + E) log V) with a binary heap |
| Approach | Dynamic programming: relax all edges repeatedly | Greedy: always expand the closest unfinished node |
| Use when | Weights can be negative, or you need cycle detection | All weights are 0 or positive (maps, networks) |
If every edge has the same weight, plain BFS is faster still; see BFS vs DFS. For non-negative weights, see Dijkstra's algorithm.
Complexity
- Time: O(V·E) in the worst case (V−1 passes over E edges). With the early stop, often much less: our 5-node example finished in 3 passes.
- Space: O(V) for distances and previous nodes.
For a refresher on the notation, see Big-O notation.
Where Bellman-Ford Is Used
- Distance-vector routing (RIP): each router shares its distance table with neighbors, a distributed form of the same relaxation.
- Arbitrage detection in exchange rates, as above.
- Constraint systems: "x − y ≤ c" constraints (scheduling with time windows) become a graph; a negative cycle means the constraints can't all be met.
- Johnson's algorithm for all-pairs shortest paths on sparse graphs runs Bellman-Ford once to reweight edges, then Dijkstra from every node.
For the bigger picture of graph algorithms, see our graph data structures guide and Kruskal's algorithm for minimum spanning trees.
FAQs
Why does Bellman-Ford run V−1 times?
A shortest path that doesn't repeat nodes has at most V−1 edges, and each pass is guaranteed to fix at least the next edge of every shortest path.
Can Bellman-Ford handle negative weights?
Yes, that's its purpose. It can't produce shortest paths when there's a negative cycle, but it detects that case.
How does Bellman-Ford detect a negative cycle?
After V−1 passes, it relaxes every edge once more. If any distance still decreases, a negative cycle is reachable from the source.
Is Bellman-Ford greedy or dynamic programming?
Dynamic programming: after k passes, every node has the shortest distance using at most k edges. Dijkstra is the greedy one.
Does Bellman-Ford work on undirected graphs?
Only if all weights are non-negative, and then Dijkstra is faster. Any negative undirected edge forms a negative cycle by itself.
What is the time complexity of Bellman-Ford?
O(V·E) time and O(V) space.
Related Articles
View allAbout Muhaymin Bin Mehmood
Front-end Developer skilled in the MERN stack, experienced in web and mobile development. Proficient in React.js, Node.js, and Express.js, with a focus on client interactions, sales support, and high-performance applications.




