Why Bellman Ford Algorithm Negative Weights in DSA Javascript?

The Big Idea

What if some roads actually pay you to travel them? How do you find the cheapest path then?

The Scenario

Imagine you have a map with cities connected by roads, some roads have tolls that can actually give you money back (negative cost). You want to find the cheapest way to travel from one city to all others.

The Problem

Trying to find the cheapest path by checking all routes manually is slow and confusing, especially when some roads reduce your cost. You might miss cheaper paths or get stuck in loops.

The Solution

The Bellman Ford algorithm smartly checks all roads multiple times to find the cheapest paths, even when some roads have negative costs. It also detects if there is a loop that keeps reducing cost endlessly.

Before vs After

✗ Before

function findCheapestPath(graph, start) {
  // Manually check all paths, very complex and slow
  // No clear way to handle negative costs
}

✓ After

function bellmanFord(graph, start) {
  // Initialize distances
  // Relax edges repeatedly
  // Detect negative cycles
}

What It Enables

You can reliably find shortest paths in graphs with negative weights and know if a negative cycle exists.

Real Life Example

Calculating the cheapest cost to send packages between cities where some routes offer discounts or rebates.

Key Takeaways

Manual path checking is slow and error-prone with negative weights.

Bellman Ford handles negative weights and detects negative cycles.

It ensures correct shortest paths even with tricky costs.

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