Bellman-Ford solves the single-source shortest-path problem while supporting negative edge weights.

It can also detect a negative-weight cycle that is reachable from the source.

This makes Bellman-Ford useful when Dijkstra's non-negative-weight assumption does not hold.

Core idea: relaxation

For an edge:

u → v
weight = w

if:

dist[u] + w < dist[v]

then a better path to v has been found:

dist[v] = dist[u] + w

Bellman-Ford repeatedly relaxes every edge.

Initialization

dist[source] = 0
all other distances = Infinity

Why V-1 passes?

A simple shortest path in a graph with V vertices contains at most V-1 edges.

After repeated relaxation, shortest-path information can propagate through paths of increasing length.

Therefore V-1 full passes are sufficient when no reachable negative cycle exists.

JavaScript

function bellmanFord(vertices, edges, source) {
  const dist = Object.fromEntries(
    vertices.map(v => [v, Infinity])
  );

  dist[source] = 0;

  for (let i = 0; i < vertices.length - 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;
      }
    }

    if (!updated) break;
  }

  for (const [u, v, w] of edges) {
    if (
      dist[u] !== Infinity &&
      dist[u] + w < dist[v]
    ) {
      throw new Error(
        "Negative cycle reachable from source"
      );
    }
  }

  return dist;
}

Negative edges vs negative cycles

A negative edge is not automatically a problem.

A negative cycle is different: its total weight is below zero.

Traversing such a cycle repeatedly can reduce total path cost without bound, so a finite shortest path is not defined for affected vertices.

Detecting a negative cycle

After V-1 rounds, perform one additional pass.

If any reachable edge can still be relaxed, a reachable negative cycle exists.

The reachability condition matters: a negative cycle in a disconnected part of the graph does not affect single-source distances.

Detecting any negative cycle in the whole graph

Add a virtual super-source with zero-weight edges to every vertex, then run Bellman-Ford from that source.

This makes every component reachable.

Reconstructing paths

Store a parent during relaxation:

parent[v] = u

Then walk backward from a target to the source.

Early stopping

If a full pass performs no update, all distances have converged and the remaining rounds can be skipped.

This does not change the worst-case complexity but can improve practical runtime.

Bellman-Ford vs Dijkstra

| Feature | Bellman-Ford | Dijkstra | |---|---|---| | Negative edges | Supported | Not in standard form | | Negative-cycle detection | Yes | No | | Typical complexity | O(VE) | O((V+E) log V) | | Main strategy | repeated relaxation | greedy priority queue |

Dijkstra is usually preferable when all edge weights are non-negative.

Bellman-Ford vs BFS

Use BFS when the graph is unweighted or all edge costs are equal.

Use Bellman-Ford when edge weights vary and negative weights may occur.

DAG shortest paths

If the graph is a DAG, topological ordering plus edge relaxation solves shortest paths in:

O(V + E)

even with negative edges.

So Bellman-Ford is not always the best choice for negative weights.

Floyd-Warshall and Johnson

Bellman-Ford is single-source.

Floyd-Warshall solves all-pairs shortest paths in O(V³).

Johnson's algorithm uses Bellman-Ford for reweighting, then runs Dijkstra from every vertex, making it useful for sparse all-pairs graphs with negative edges but no negative cycle.

Distance-vector routing

Bellman-Ford's relaxation principle underlies distance-vector routing ideas.

A router updates its estimated distance to a destination using neighbors' advertised distances.

Conceptually:

best route =
min(
  link cost to neighbor
  +
  neighbor's distance
)

Difference constraints

Constraints such as:

x_v <= x_u + w

can be modeled as weighted directed edges.

Bellman-Ford can help test feasibility; a negative cycle can indicate inconsistent constraints.

Undirected negative edges

An undirected negative edge is especially important.

Representing:

u -- v = -5

as two directed edges gives:

u → v = -5
v → u = -5

which creates a negative two-edge cycle.

Edge cases

• unreachable vertices remain Infinity,
• invalid source should be validated,
• duplicate edges are allowed,
• a negative self-loop is a negative cycle,
• very large numeric values require care,
• negative cycles matter only if reachable unless a super-source is used.

TypeScript

type Vertex = string;

type Edge = [
  from: Vertex,
  to: Vertex,
  weight: number
];

type BellmanFordResult =
  | {
      ok: true;
      dist: Map<Vertex, number>;
      parent: Map<Vertex, Vertex | null>;
    }
  | {
      ok: false;
      reason: "INVALID_SOURCE" | "NEGATIVE_CYCLE";
      dist?: Map<Vertex, number>;
      parent?: Map<Vertex, Vertex | null>;
    };

function bellmanFord(
  vertices: Vertex[],
  edges: Edge[],
  source: Vertex
): BellmanFordResult {
  const dist = new Map<Vertex, number>();
  const parent =
    new Map<Vertex, Vertex | null>();

  for (const v of vertices) {
    dist.set(v, Infinity);
    parent.set(v, null);
  }

  if (!dist.has(source)) {
    return {
      ok: false,
      reason: "INVALID_SOURCE"
    };
  }

  dist.set(source, 0);

  for (let i = 0; i < vertices.length - 1; i++) {
    let updated = false;

    for (const [u, v, w] of edges) {
      const du = dist.get(u)!;
      const dv = dist.get(v)!;

      if (
        du !== Infinity &&
        du + w < dv
      ) {
        dist.set(v, du + w);
        parent.set(v, u);
        updated = true;
      }
    }

    if (!updated) break;
  }

  for (const [u, v, w] of edges) {
    const du = dist.get(u)!;
    const dv = dist.get(v)!;

    if (
      du !== Infinity &&
      du + w < dv
    ) {
      return {
        ok: false,
        reason: "NEGATIVE_CYCLE",
        dist,
        parent
      };
    }
  }

  return {
    ok: true,
    dist,
    parent
  };
}

Complexity

Time:  O(VE)
Space: O(V)

excluding graph storage.

Common mistakes

• performing too few passes,
• forgetting the extra negative-cycle check,
• confusing a negative edge with a negative cycle,
• reporting unreachable negative cycles in single-source mode,
• using Bellman-Ford unnecessarily on non-negative graphs,
• forgetting parent data when path reconstruction is required,
• overlooking the implication of negative edges in undirected graphs.

Summary

Bellman-Ford repeatedly relaxes all edges.

After V-1 passes, shortest paths are known if no reachable negative cycle exists.

One additional successful relaxation proves a negative cycle.

Use it when:

single-source shortest path
+ possible negative weights
+ possible negative-cycle detection

are part of the problem.