The Bellman-Ford algorithm is a classic algorithm used to compute the shortest path from a single source to all other nodes in a graph.
Unlike Dijkstra’s algorithm, Bellman-Ford can handle negative edge weights and can detect negative cycles, making it useful for more complex graph problems.

It runs slower than Dijkstra, but its flexibility makes it valuable when dealing with tricky graphs.

When to Use Bellman-Ford

Bellman-Ford is the right choice if:

• Your graph contains negative edges
• You need to detect negative cycles
• Dijkstra’s algorithm cannot be used safely

Use Dijkstra when all weights are non-negative and speed matters.
Use Bellman-Ford when correctness in the presence of negative edges matters.

How Bellman-Ford Works

The algorithm performs edge relaxation repeatedly:

Step 1 — Initialize distances

• Set the source node’s distance to 0
• Set all other distances to Infinity

Step 2 — Relax all edges V - 1 times

For a graph with V vertices, the longest possible shortest path has V - 1 edges.

So, we repeat:
For each edge (u → v) with weight w:
If: dist[u] + w < dist[v] then update:
dist[v] = dist[u] + w

Step 3 — Detect negative cycles

Run one more relaxation pass:

• If any distance can still be improved → negative cycle exists

This makes Bellman-Ford valuable for real-world problems like detecting financial arbitrage.

Bellman-Ford Implementation (JavaScript)

function bellmanFord(vertices, edges, source) {
  const dist = Array(vertices).fill(Infinity);
  dist[source] = 0;

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

  // Step 2: Check for negative cycles
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      console.log("Graph contains a negative weight cycle!");
      return null;
    }
  }

  return dist;
}

// Example graph
// vertices = 5 (nodes 0-4)
// edges = [u, v, weight]
const edges = [
  [0, 1, 6],
  [0, 2, 7],
  [1, 2, 8],
  [1, 3, 5],
  [1, 4, -4],
  [2, 3, -3],
  [2, 4, 9],
  [3, 1, -2],
  [4, 0, 2],
  [4, 3, 7]
];

const result = bellmanFord(5, edges, 0);

console.log(result);

// Expected Output:
// [0, 2, 7, 4, -2]`}

Example Explained

For the example graph:

• Distance to node 1 becomes 2
• Distance to node 3 becomes 4
• Distance to node 4 becomes -2

The algorithm ensures that all shortest paths are found even with negative edges, as long as no negative cycle exists.

Detecting Negative Cycles

If after completing the (V - 1) relaxations, you can still improve the distance of any node:

A negative cycle is present.

In such a case, shortest paths are undefined — following the cycle would infinitely reduce the path cost.

Time and Space Complexity

Bellman-Ford is slower than Dijkstra (O(E log V) with a priority queue), but it is more powerful because it supports negative weights and cycle detection.

When NOT to Use Bellman-Ford

Avoid Bellman-Ford when:

• All edge weights are non-negative
  → Use Dijkstra instead (much faster)

• Your graph is extremely large
  → Bellman-Ford may be too slow