Suggest an edit

Improve this article

Refine the answer for “What does the Bellman-Ford algorithm do on graphs?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

The Bellman-Ford algorithm finds the shortest paths from a single source vertex in a weighted directed graph, correctly handles negative weights, and can detect reachable negative cycles.

## In detail

This is the classic single-source shortest-path algorithm, which repeatedly "relaxes" (improves) distance estimates by going through all the edges of the graph. Unlike Dijkstra, it handles negative weights and can report that no correct shortest paths exist if a negative cycle is reachable from the source.

### What it can do

- Finds shortest paths from a single vertex (single-source shortest paths, SSSP).
- Correctly handles negative edge weights.
- Detects negative cycles reachable from the source (with a negative total weight).
- Suits directed graphs; for undirected ones, each edge is represented as two directed edges.

### When to use it

- Shortest paths are needed when negative weights are present.
- Negative cycles reachable from the source need to be detected.
- The graph is not too large (the algorithm is slower than Dijkstra).

### Limitations and complexity

- Time: O(V · E), where V is the number of vertices and E the number of edges.
- Memory: O(V).
- If a negative cycle is reachable from the source, no correct final distances exist, the algorithm detects and reports this.

## Idea of the algorithm

1. Initialization: distance to the source = 0, to the rest = +∞; parents unknown.
2. Repeat V-1 times: go through all edges (u → v, w) and try to improve dist[v] via u. This is "relaxing" an edge: if dist[u] + w < dist[v], update dist[v] and remember the parent v = u.
3. Check for a negative cycle: make one more pass over the edges. If some distance still improves, a reachable negative cycle exists.

## Example (without a negative cycle)

Vertices: S=0, A=1, B=2, C=3. Edges: S→A (4), S→B (5), A→B (−2), B→C (3), A→C (4).

- Start: dist = [0, +∞, +∞, +∞].
- After the iterations: dist[A]=4 (S→A), dist[B]=2 (S→A→B with weights 4 + (−2)), dist[C]=5 (better via B: 2 + 3).

## Example of detecting a negative cycle

Vertices: S=0, A=1, B=2, C=3. Edges: S→A (1), A→B (1), B→C (1), C→A (−4). The cycle A→B→C→A has a total weight of −2, the algorithm will detect it on the extra pass.

## Code in JavaScript (ES6)

```javascript
/*
Bellman-Ford: shortest paths from source s in a graph with n vertices and a list of edges.
Edges: an array of objects { u, v, w }, from u to v with weight w.
Returns: { dist, parent, negativeCycle, cycle }.
*/
function bellmanFord(n, edges, s) {
  const INF = Number.POSITIVE_INFINITY;
  const dist = Array(n).fill(INF);
  const parent = Array(n).fill(null);
  dist[s] = 0;

// V-1 iterations of relaxation
  for (let i = 0; i < n - 1; i++) {
    let updated = false;
    for (const { u, v, w } of edges) {
      if (dist[u] !== INF && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        updated = true;
      }
    }
    if (!updated) break; // early exit if already stable
  }

// Checking for a negative cycle (extra pass)
  let x = -1;
  for (const { u, v, w } of edges) {
    if (dist[u] !== INF && dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w; // formally still improved
      parent[v] = u;
      x = v; // the vertex improved on the (V)-th iteration
    }
  }

let negativeCycle = false;
  let cycle = [];
  if (x !== -1) {
    negativeCycle = true;
    // Find a vertex guaranteed to lie on the cycle
    let y = x;
    for (let i = 0; i < n; i++) y = parent[y];

// Reconstruct the cycle by walking parent until returning to y
    const stack = [];
    let cur = y;
    do {
      stack.push(cur);
      cur = parent[cur];
    } while (cur !== y && stack.length <= n + 5);
    stack.push(y);
    cycle = stack.reverse(); // the cycle as a sequence of vertices
  }

return { dist, parent, negativeCycle, cycle };
}

// Example usage (without a negative cycle)
const n1 = 4; // 0:S, 1:A, 2:B, 3:C
const edges1 = [
  { u: 0, v: 1, w: 4 },
  { u: 0, v: 2, w: 5 },
  { u: 1, v: 2, w: -2 },
  { u: 2, v: 3, w: 3 },
  { u: 1, v: 3, w: 4 },
];
console.log('Example 1:', bellmanFord(n1, edges1, 0));

// Example with a negative cycle
const n2 = 4; // 0:S, 1:A, 2:B, 3:C
const edges2 = [
  { u: 0, v: 1, w: 1 },
  { u: 1, v: 2, w: 1 },
  { u: 2, v: 3, w: 1 },
  { u: 3, v: 1, w: -4 }, // cycle A->B->C->A with sum -2
];
console.log('Example 2:', bellmanFord(n2, edges2, 0));
```

## Code walkthrough

- Parameters: n, the number of vertices (indices 0..n-1); edges, the list of edges {u,v,w}; s, the source.
- dist, the array of distances; parent, for path reconstruction.
- negativeCycle, a flag for whether a reachable negative cycle exists; cycle, one found loop (a sequence of vertices).
- Optimization: an early exit if no improvements happened during an iteration.

## Comparison with Dijkstra in a nutshell

- Dijkstra: faster (O((V+E) log V)), but only works with non-negative weights (without special tricks).
- Bellman-Ford: slower (O(V·E)), but supports negative weights and detects negative cycles.

## Important nuances for an interview

- The graph is most often represented as an edge list: convenient, since the algorithm iterates over edges.
- Initialization: dist[source]=0, the rest +∞; parent[source]=null.
- If a negative cycle is reachable, no correct final distances exist; you either need to report this or mark the corresponding vertices as "minus infinity".
- It can be sped up on "sparse" graphs with an early exit when there are no updates.
- For a DAG, shortest paths are found faster via the topological order.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts991 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.