jsschools

Bellman-Ford Algorithm

Single-source shortest paths algorithm that handles negative edge weights and detects negative-weight cycles by relaxing all edges V-1 times.

Spec ↗

Syntax

bellmanFord(edges, V, src)

Parameters

NameTypeRequiredDescription
edges Array<{u: number, v: number, w: number}> Yes List of directed edges. Each edge has source u, destination v, and weight w.
V number Yes Total number of vertices (0-indexed).
src number Yes Source vertex. Distance from src to itself is 0.

Returns

number[] | null — Array of shortest distances indexed by vertex, or null if a negative cycle is reachable.

Examples

function bellmanFord(edges, V, src) {
  const dist = new Array(V).fill(Infinity);
  dist[src] = 0;

  for (let i = 0; i < V - 1; i++) {
    for (const { u, v, w } of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Check for negative cycles
  for (const { u, v, w } of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) return null;
  }
  return dist;
}

const edges = [
  {u:0,v:1,w:4},{u:0,v:2,w:5},{u:1,v:3,w:3},
  {u:2,v:1,w:-4},{u:3,v:2,w:-1},
];
console.log(bellmanFord(edges, 4, 0));
Output 
[ 0, 1, 5, 4 ]

// Negative cycle detection
function bellmanFord(edges, V, src) {
  const dist = new Array(V).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i < V - 1; i++)
    for (const {u,v,w} of edges)
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  for (const {u,v,w} of edges)
    if (dist[u] + w < dist[v]) return null; // negative cycle
  return dist;
}

const negCycle = [{u:0,v:1,w:1},{u:1,v:2,w:-3},{u:2,v:0,w:1}];
console.log(bellmanFord(negCycle, 3, 0));
Output 
null

Notes

| Case | Time | Space | |---------|---------|-------| | Best | O(VE) | O(V) | | Average | O(VE) | O(V) | | Worst | O(VE) | O(V) | Bellman-Ford is slower than Dijkstra (O(VE) vs O((V+E) log V)) but handles negative weights. If the (V)th relaxation pass still reduces any distance, a negative cycle exists and shortest paths are undefined. The algorithm can be terminated early if no relaxation occurs in a pass. SPFA (Shortest Path Faster Algorithm) is a queue-based optimisation that runs faster in practice but shares the same worst-case complexity.

See also