Bellman–Ford

How it works, step by step

1. 1

   Set the start's distance to 0 and every other node to infinity (not reached yet).

2. 2

   Walk the edge list in a fixed order. For each edge u→v with weight w: if `dist[u] + w < dist[v]`, write the smaller value. This check is called relaxing the edge.

3. 3

   One full sweep over all edges is one iteration. Each iteration lets the best-known costs travel at least one edge further from the start.

4. 4

   Repeat up to V-1 times. A shortest path can use at most V-1 edges, so that is always enough - no matter how unlucky the edge order is.

5. 5

   If an iteration improves nothing, stop early. A second identical sweep would see the same numbers and change nothing either.

6. 6

   Safety check: run one extra iteration. If anything still improves, the graph has a negative cycle and 'shortest path' has no meaning.

The code, in JavaScript

function bellmanFord(nodes, edges, start) {
  const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));
  dist[start] = 0;

  // A shortest path uses at most V-1 edges, so V-1 sweeps always suffice.
  for (let i = 0; i < nodes.length - 1; i++) {
    let improved = false;

    for (const [from, to, w] of edges) {
      // Relax: can from's best cost plus this edge beat to's best?
      // Infinity + w is still Infinity, so unreached nodes offer nothing.
      if (dist[from] + w < dist[to]) {
        dist[to] = dist[from] + w;
        improved = true;
      }
    }

    if (!improved) break;   // a full sweep changed nothing → we are done
  }

  return dist;
}

const edges = [
  ["A", "B", 3], ["A", "C", 9], ["B", "D", 5],
  ["C", "D", -4],              // negative edge: D is cheapest via C
  ["D", "E", 2], ["D", "F", 6], ["E", "F", 3],
];

bellmanFord(["A", "B", "C", "D", "E", "F"], edges, "A");
// → { A: 0, B: 3, C: 9, D: 5, E: 7, F: 10 }

Dry run: Bellman-Ford from node A

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• It relaxes edges, not nodes. There is no queue and no visiting order - people carry over their Dijkstra mental model and add one, which either breaks correctness on negatives or quietly rebuilds Dijkstra.
• V-1 iterations is the worst case, not the plan. With the early-exit flag most graphs settle in a few sweeps - forget the flag and every run pays the worst case.
• A negative edge is fine; a negative cycle is fatal - one more lap is always cheaper, so 'shortest' stops existing. On untrusted input, always run the one extra detection pass.
• `Infinity + w` is still `Infinity` in JavaScript, so unreached nodes offer nothing. Swap Infinity for a big number like 1e9 and `1e9 + w` suddenly wins comparisons - inventing paths out of unreachable nodes.

Bellman–Ford vs. its closest relatives