Bellman Ford Algorithm Negative Weights in DSA Javascript

Mental Model

Bellman Ford finds shortest paths from one point to all others even if some paths have negative costs, by relaxing edges multiple times.

Analogy: Imagine you want to find the cheapest way to travel between cities, but some roads give you discounts (negative costs). You check all roads repeatedly to update your best prices until no cheaper route is found.

Graph with nodes and edges:

  (A)
  / \
-1   4
 /     \
(B)---(C)
  \    /
   2  -3
    \ /
    (D)

Edges have weights including negative ones (-1, -3).

Dry Run Walkthrough

Input: Graph with edges: A->B(-1), A->C(4), B->C(3), B->D(2), D->B(1), D->C(-3); start at A

Goal: Find shortest distances from A to all nodes, handling negative weights correctly

Step 1: Initialize distances: A=0, others=∞

Distances: A=0, B=∞, C=∞, D=∞

Why: Start with zero distance to source and unknown distances to others

Step 2: Relax edge A->B(-1): update B from ∞ to 0 + (-1) = -1

Distances: A=0, B=-1, C=∞, D=∞

Why: Found a cheaper path to B through A

Step 3: Relax edge A->C(4): update C from ∞ to 0 + 4 = 4

Distances: A=0, B=-1, C=4, D=∞

Why: Found a path to C through A

Step 4: Relax edge B->C(3): update C from 4 to -1 + 3 = 2

Distances: A=0, B=-1, C=2, D=∞

Why: Found a cheaper path to C through B

Step 5: Relax edge B->D(2): update D from ∞ to -1 + 2 = 1

Distances: A=0, B=-1, C=2, D=1

Why: Found a path to D through B

Step 6: Relax edge D->B(1): no update since B=-1 < 1+1=2

Distances: A=0, B=-1, C=2, D=1

Why: No cheaper path to B found

Step 7: Relax edge D->C(-3): update C from 2 to 1 + (-3) = -2

Distances: A=0, B=-1, C=-2, D=1

Why: Found a cheaper path to C through D

Step 8: Repeat relaxation for all edges to confirm no further updates

Distances remain: A=0, B=-1, C=-2, D=1

Why: No changes means shortest paths found

Result:

Distances: A=0, B=-1, C=-2, D=1

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.edges = [];
  }

  addEdge(u, v, w) {
    this.edges.push({ u, v, w });
  }

  bellmanFord(src) {
    const dist = Array(this.V).fill(Infinity);
    dist[src] = 0;

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

    // Check for negative weight cycles
    for (const edge of this.edges) {
      const { u, v, w } = edge;
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        throw new Error('Graph contains negative weight cycle');
      }
    }

    return dist;
  }
}

// Driver code
const graph = new Graph(4);
graph.addEdge(0, 1, -1); // A->B
graph.addEdge(0, 2, 4);  // A->C
graph.addEdge(1, 2, 3);  // B->C
graph.addEdge(1, 3, 2);  // B->D
graph.addEdge(3, 1, 1);  // D->B
graph.addEdge(3, 2, -3); // D->C

try {
  const distances = graph.bellmanFord(0); // source A=0
  for (let i = 0; i < distances.length; i++) {
    console.log(`Distance from A to ${String.fromCharCode(65 + i)} is ${distances[i]}`);
  }
} catch (e) {
  console.log(e.message);
}

dist[src] = 0;

Initialize source distance to zero

for (let i = 1; i <= this.V - 1; i++) {

Repeat relaxation V-1 times to propagate shortest paths

if (dist[u] !== Infinity && dist[u] + w < dist[v]) {

Relax edge if shorter path found

dist[v] = dist[u] + w;

Update distance to vertex v

for (const edge of this.edges) { if (dist[u] !== Infinity && dist[u] + w < dist[v]) { throw new Error('Graph contains negative weight cycle'); } }

Detect negative weight cycle by checking for further relaxations

Output

Distance from A to A is 0

Distance from A to B is -1

Distance from A to C is -2

Distance from A to D is 1

Complexity Analysis

Time: O(V * E) because we relax all edges V-1 times, where V is vertices and E is edges

Space: O(V) to store distances for each vertex

vs Alternative: Dijkstra's algorithm is faster O(E + V log V) but cannot handle negative weights; Bellman Ford handles negatives but is slower

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and throws error

DSA Javascript

if (dist[u] !== Infinity && dist[u] + w < dist[v]) { throw new Error('Graph contains negative weight cycle'); }

Graph with no edges

Distances remain infinity except source which is zero

DSA Javascript

dist[src] = 0;

Single vertex graph

Distance to itself is zero, no edges to relax

DSA Javascript

dist[src] = 0;

When to Use This Pattern

When you need shortest paths but edges can have negative weights, use Bellman Ford because it handles negatives and detects cycles.

Common Mistakes

Mistake: Not repeating relaxation V-1 times, missing updates from longer paths
Fix: Ensure the outer loop runs exactly V-1 times to propagate shortest paths fully

Mistake: Not checking for negative weight cycles after relaxation
Fix: Add a final check to detect cycles by trying one more relaxation

Summary

Finds shortest paths from one node to all others even with negative edge weights.

Use when graph edges can have negative weights and you need to detect negative cycles.

Relax all edges repeatedly to update shortest paths until no improvements remain.

Practice

1. What is the main purpose of the Bellman-Ford algorithm in graphs with negative weights?

easy

A. To sort vertices in topological order

B. To find the longest path in a graph

C. To detect cycles in an undirected graph

D. To find the shortest path from a single source to all vertices, even with negative weights

Solution

1. Step 1: Understand Bellman-Ford's goal

   The algorithm finds shortest paths from one source vertex to all others, handling negative weights.

2. Step 2: Compare with other algorithms

   Dijkstra's algorithm cannot handle negative weights, but Bellman-Ford can and also detects negative cycles.

3. Final Answer:

   To find the shortest path from a single source to all vertices, even with negative weights -> Option D

4. Quick Check:

   Bellman-Ford finds shortest paths with negative weights [OK]

Hint: Bellman-Ford handles negative weights and finds shortest paths [OK]

Common Mistakes:

• Confusing Bellman-Ford with Dijkstra's algorithm
• Thinking it finds longest paths
• Assuming it only detects cycles

2. Which of the following is the correct way to initialize the distance array in Bellman-Ford algorithm in JavaScript?

easy

A. const dist = new Array(V).fill(0); dist[source] = 1;

B. const dist = Array(V).map(() => 0); dist[source] = Infinity;

C. const dist = new Array(V).fill(Infinity); dist[source] = 0;

D. const dist = new Array(V).fill(-1); dist[source] = 0;

Solution

1. Step 1: Initialize distances to Infinity

   All vertices except the source start with distance Infinity to represent unknown paths.

2. Step 2: Set source distance to zero

   The source vertex distance is zero because the path from source to itself is zero.

3. Final Answer:

   const dist = new Array(V).fill(Infinity); dist[source] = 0; -> Option C

4. Quick Check:

   Distance array initialized with Infinity except source = 0 [OK]

Hint: Initialize all distances to Infinity except source as 0 [OK]

Common Mistakes:

• Filling array with zeros instead of Infinity
• Setting source distance to Infinity
• Using map without fill causing undefined values

3. Consider the following graph edges and weights:
edges = [[0,1,4],[0,2,5],[1,2,-3],[2,3,4]]
Using Bellman-Ford from source 0, what is the distance array after all relaxations?

medium

A. [0, 4, 1, 5]

B. [0, 4, 5, 9]

C. [0, 4, -3, 1]

D. [0, 4, 1, 9]

Solution

1. Step 1: Initialize distances

   dist = [0, Infinity, Infinity, Infinity]

2. Step 2: Relax edges |V|-1 = 3 times

   First iteration:
   - (0,1,4): dist[1] = 0 + 4 = 4
   - (0,2,5): dist[2] = 0 + 5 = 5
   - (1,2,-3): dist[2] = min(5, 4 + (-3)) = 1
   - (2,3,4): dist[3] = 1 + 4 = 5
   dist = [0,4,1,5]
   Second and third iterations: no updates.

3. Final Answer:

   [0, 4, 1, 5] -> Option A

4. Quick Check:

   Distances after relaxations = [0,4,1,5] [OK]

Hint: Relax edges V-1 times updating distances [OK]

Common Mistakes:

• Not relaxing edges enough times
• Ignoring negative weight edge effect
• Incorrectly updating distances

4. The following code snippet attempts to implement Bellman-Ford but has a bug. What is the error?

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

medium

A. The outer loop should run V-1 times, not V times

B. The inner loop should iterate over vertices, not edges

C. The condition should be dist[v] + w < dist[u]

D. dist array is not initialized before the loops

Solution

1. Step 1: Check loop iteration count

   Bellman-Ford requires relaxing edges exactly V-1 times to find shortest paths.

2. Step 2: Identify off-by-one error

   The code runs the outer loop V times, which is one extra iteration and may cause incorrect behavior or unnecessary work.

3. Final Answer:

   The outer loop should run V-1 times, not V times -> Option A

4. Quick Check:

   Outer loop runs V-1 times in Bellman-Ford [OK]

Hint: Outer loop must run V-1 times for correct relaxation [OK]

Common Mistakes:

• Running outer loop V times instead of V-1
• Mixing up edge and vertex iteration
• Wrong relaxation condition

5. Given a graph with edges
edges = [[0,1,1],[1,2,-1],[2,3,-1],[3,1,-1]]
and source 0, what does Bellman-Ford detect after running all relaxations?

hard

A. No negative cycle detected; shortest distances computed

B. Negative cycle detected reachable from source

C. Algorithm fails due to zero-weight cycle

D. Distances remain Infinity for all vertices except source

Solution

1. Step 1: Analyze the cycle in the graph

   The edges (1->2), (2->3), (3->1) form a cycle with total weight -3 (negative cycle).

2. Step 2: Bellman-Ford detects negative cycles

   After V-1 relaxations, one more iteration finds further distance reductions, indicating a negative cycle reachable from source.

3. Final Answer:

   Negative cycle detected reachable from source -> Option B

4. Quick Check:

   Negative cycle detection triggers on further relaxation [OK]

Hint: Extra relaxation detects negative cycles reachable from source [OK]

Common Mistakes:

• Ignoring negative cycle presence
• Assuming zero-weight cycles cause failure
• Thinking distances remain Infinity