Bellman Ford Algorithm Negative Weights in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bellman-Ford on a graph with negative weights

What is the output distances array after running Bellman-Ford algorithm on the given graph from source node 0?

DSA Javascript

const edges = [
  [0, 1, 4],
  [0, 2, 5],
  [1, 2, -3],
  [2, 3, 4],
  [3, 1, 6]
];
const V = 4;
const source = 0;

function bellmanFord(V, edges, source) {
  const dist = Array(V).fill(Infinity);
  dist[source] = 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;
      }
    }
  }

  return dist;
}

console.log(bellmanFord(V, edges, source));

A [0, 4, 1, 5]

B [0, 4, 5, 9]

C [0, -2, 1, 5]

D [0, Infinity, Infinity, Infinity]

💡 Hint

Remember Bellman-Ford relaxes edges V-1 times and updates distances if a shorter path is found.

The algorithm starts with distance 0 at source 0. It relaxes edges and finds that node 2 can be reached via node 1 with a shorter path (4 + -3 = 1). Node 3 is reached from node 2 with distance 1 + 4 = 5. Node 1 remains at distance 4. So final distances are [0, 4, 1, 5].

🧠 Conceptual

intermediate

Detecting negative weight cycles with Bellman-Ford

After running Bellman-Ford algorithm, how can you detect if the graph contains a negative weight cycle?

A If the source node distance becomes negative, there is a negative weight cycle.

B If the sum of all edge weights is negative, the graph has a negative weight cycle.

C If any distance can still be updated after V-1 iterations, a negative weight cycle exists.

D If the graph has any edge with negative weight, it must have a negative weight cycle.

💡 Hint

Bellman-Ford runs V-1 times to relax edges. Extra relaxation means cycle.

After V-1 iterations, all shortest paths should be found. If any edge can still reduce a distance, it means a cycle with negative total weight exists that can be traversed indefinitely to reduce path cost.

🔧 Debug

advanced

Identify the bug in this Bellman-Ford implementation

What error or issue will this code produce when run on a graph with negative weights?

DSA Javascript

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

  for (let i = 0; i < V; i++) {  // Loop runs V times instead of V-1
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {  // Added missing check if dist[u] is Infinity
        dist[v] = dist[u] + w;
      }
    }
  }
  return dist;
}

A No error; code runs correctly and detects negative cycles

B Distances may become negative Infinity causing incorrect results

C TypeError because dist[u] can be Infinity and adding w causes invalid comparison

D Algorithm runs extra iteration but still produces correct shortest paths

💡 Hint

Observe the loop condition (V vs V-1) and the relaxation if statement.

The loop runs V times instead of V-1, performing one extra relaxation iteration. In graphs without negative weight cycles, no further updates occur after V-1 iterations, so the shortest paths remain correct. The missing dist[u] !== Infinity check does not cause runtime errors or incorrect updates in JavaScript, since Infinity + w evaluates to Infinity and comparisons behave as expected.

🚀 Application

advanced

Using Bellman-Ford to find shortest paths in a weighted directed graph

Given a weighted directed graph with possible negative edges but no negative cycles, which of the following is the correct output of Bellman-Ford from source 0?

DSA Javascript

const edges = [
  [0, 1, 1],
  [1, 2, -1],
  [2, 3, -1],
  [3, 4, -1],
  [4, 1, 3]
];
const V = 5;
const source = 0;

function bellmanFord(V, edges, source) {
  const dist = Array(V).fill(Infinity);
  dist[source] = 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;
      }
    }
  }

  return dist;
}

console.log(bellmanFord(V, edges, source));

A [0, 1, 0, -1, 0]

B [0, 1, 0, -1, -2]

C [0, 1, 1, 0, -1]

D [0, Infinity, Infinity, Infinity, Infinity]

💡 Hint

Relax edges multiple times to propagate negative weights correctly.

The path from 0 to 1 costs 1, then 1 to 2 costs -1 (total 0), 2 to 3 costs -1 (total -1), 3 to 4 costs -1 (total -2). The edge 4 to 1 with weight 3 does not create a negative cycle and does not reduce distances further.

🧠 Conceptual

expert

Why Bellman-Ford is preferred over Dijkstra for graphs with negative weights

Which statement best explains why Bellman-Ford algorithm is used instead of Dijkstra's algorithm on graphs with negative edge weights?

A Bellman-Ford correctly handles negative weights by relaxing edges multiple times, while Dijkstra assumes all weights are non-negative and can give wrong results otherwise.

B Bellman-Ford uses less memory than Dijkstra, making it better for large graphs.

C Dijkstra cannot be implemented for directed graphs, but Bellman-Ford can.

D Bellman-Ford is faster than Dijkstra on all graphs, so it is preferred.

💡 Hint

Think about how each algorithm treats edge weights and updates distances.

Dijkstra's algorithm assumes all edge weights are non-negative to guarantee that once a node's shortest distance is found, it won't be updated. Negative weights break this assumption, causing Dijkstra to produce incorrect results. Bellman-Ford relaxes edges multiple times and can handle negative weights correctly.

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