Bellman Ford Algorithm Negative Weights in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with Infinity for all vertices except the source.

DSA Javascript

const distances = Array(vertices).fill([1]);
distances[source] = 0;

Drag options to blanks, or click blank then click option'

A-Infinity

B0

CInfinity

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for all distances causes incorrect shortest path calculations.

Using null or -Infinity is not appropriate for initial distances.

We use Infinity to represent initially unknown distances, except the source which is 0.

2fill in blank

medium

Complete the code to relax edges inside the main loop of Bellman-Ford.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A>

B<

C===

D!==

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < reverses the logic and breaks the algorithm.

Using === or !== is incorrect for comparing distances.

We update distances[v] if the new path is shorter, so we check if distances[u] + weight < distances[v].

3fill in blank

hard

Fix the error in the negative cycle detection loop condition.

DSA Javascript

for (const [u, v, weight] of edges) {
  if (distances[u] !== Infinity && distances[u] + weight [1] distances[v]) {
    return true; // Negative cycle detected
  }
}

Drag options to blanks, or click blank then click option'

A<

B>=

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using >= or > will not correctly detect negative cycles.

Using <= reverses the logic and misses cycles.

To detect a negative cycle, we check if we can still relax an edge, meaning distances[u] + weight < distances[v].

4fill in blank

hard

Fill both blanks to complete the function signature and return statement for Bellman-Ford.

DSA Javascript

function bellmanFord([1], edges, source) {
  const distances = Array([2]).fill(Infinity);
  distances[source] = 0;
  // ... rest of the algorithm
  return distances;
}

Drag options to blanks, or click blank then click option'

Avertices

Bedges

Cvertices.length

Dsource

Attempts:

3 left

💡 Hint

Common Mistakes

Using edges or source as the size causes errors.

Using vertices.length assumes vertices is an array, but it's a number.

The function takes the number of vertices as 'vertices' and initializes distances array with that size.

5fill in blank

hard

Fill all three blanks to complete the edge relaxation and negative cycle detection in Bellman-Ford.

DSA Javascript

for (let i = 0; i < [1] - 1; i++) {
  for (const [u, v, weight] of edges) {
    if (distances[u] !== Infinity && distances[u] + weight [2] distances[v]) {
      distances[v] = distances[u] + weight;
    }
  }
}
for (const [u, v, weight] of edges) {
  if (distances[u] !== Infinity && distances[u] + weight [3] distances[v]) {
    return true; // Negative cycle detected
  }
}
return false;

Drag options to blanks, or click blank then click option'

Avertices

B<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < breaks relaxation logic.

Looping wrong number of times misses shortest paths.

We loop vertices-1 times, relax edges if new distance is less, and detect negative cycles if relaxation is still possible.

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