Bellman Ford Algorithm Negative Weights in DSA Javascript - Build from Scratch

Bellman Ford Algorithm Negative Weights

📖 Scenario: You are working on a navigation app that finds the shortest path between cities. Some roads have toll discounts, which means the cost can be negative. You need to handle these negative weights safely.

🎯 Goal: Build a program using the Bellman Ford algorithm to find the shortest distances from a starting city to all other cities, even when some roads have negative weights.

📋 What You'll Learn

Create an array called edges with exact road connections and weights

Create a variable called distance to store shortest distances initialized properly

Implement the Bellman Ford relaxation loop exactly as described

Print the final distance array showing shortest distances from the start city

💡 Why This Matters

🌍 Real World

Navigation apps and network routing often need to find shortest paths even when some routes have discounts or penalties, which can be modeled as negative weights.

💼 Career

Understanding Bellman Ford helps in roles involving graph algorithms, network optimization, and software dealing with complex pathfinding.

1

Create the graph edges array

Create an array called edges with these exact objects representing roads: {from: 0, to: 1, weight: 4}, {from: 0, to: 2, weight: 5}, {from: 1, to: 2, weight: -3}, {from: 2, to: 3, weight: 4}, {from: 3, to: 1, weight: 6}.

DSA Javascript

# Your code here

Hint

Use an array of objects. Each object has from, to, and weight keys.

2

Initialize the distance array

Create an array called distance with length 4. Set distance[0] to 0 and all other elements to Infinity.

DSA Javascript

const edges = [
  {from: 0, to: 1, weight: 4},
  {from: 0, to: 2, weight: 5},
  {from: 1, to: 2, weight: -3},
  {from: 2, to: 3, weight: 4},
  {from: 3, to: 1, weight: 6}
];
// Your code here

Hint

Distance to start city (0) is 0, others are set to Infinity.

3

Implement the Bellman Ford relaxation loop

Write a for loop that runs 3 times (one less than number of cities). Inside it, use a for loop to go through each edge in edges. If distance[edge.from] + edge.weight < distance[edge.to], update distance[edge.to] to distance[edge.from] + edge.weight.

DSA Javascript

const edges = [
  {from: 0, to: 1, weight: 4},
  {from: 0, to: 2, weight: 5},
  {from: 1, to: 2, weight: -3},
  {from: 2, to: 3, weight: 4},
  {from: 3, to: 1, weight: 6}
];

const distance = [0, Infinity, Infinity, Infinity];

// Your code here

Hint

Relax edges repeatedly to update shortest distances.

4

Print the shortest distances array

Write console.log(distance) to display the final shortest distances from city 0.

DSA Javascript

const edges = [
  {from: 0, to: 1, weight: 4},
  {from: 0, to: 2, weight: 5},
  {from: 1, to: 2, weight: -3},
  {from: 2, to: 3, weight: 4},
  {from: 3, to: 1, weight: 6}
];

const distance = [0, Infinity, Infinity, Infinity];

for (let i = 0; i < 3; i++) {
  for (const edge of edges) {
    if (distance[edge.from] + edge.weight < distance[edge.to]) {
      distance[edge.to] = distance[edge.from] + edge.weight;
    }
  }
}

// Your code here

Hint

The final distances array shows shortest paths from city 0 to all others.

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