Bellman-Ford Algorithm: Negative Weights, Cycle Detection & Code Examples

Muhaymin Bin Mehmood

Muhaymin Bin Mehmood

·
6 min read
Published Mar 10, 2025
Updated Oct 9, 2026
Bellman-Ford Algorithm: Solve Graphs with Negative Weights Banner Image
10 min read
955 words
16 sections7 code blocks

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:

Bash
A → B  6      C → D  -3
A → C  7      C → E   9
B → D  5      D → B  -2
B → E -4      E → D   7

Distances 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):

AfterABCDE
Start0∞∞∞∞
Pass 102742
Pass 20274-2
Pass 30274-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

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;
}
JavaScript
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

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

JavaScript
// 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

JavaScript
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

JavaScript
// 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 → D

We 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-FordDijkstra
Negative edgesYesNo (can give wrong answers)
Detects negative cyclesYesNo
TimeO(V·E)O((V + E) log V) with a binary heap
ApproachDynamic programming: relax all edges repeatedlyGreedy: always expand the closest unfinished node
Use whenWeights can be negative, or you need cycle detectionAll 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.

No comments yet. Be the first to comment!

Leave a Comment

2000 characters remaining

Related Articles

View all
Muhaymin Bin Mehmood

About 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.