Bellman Ford Algorithm Negative Weights in DSA Javascript - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances

↓

Repeat V-1 times: Relax all edges

↓

Check for negative weight cycles

↓

If none, shortest paths found

↓

End

Start by setting distances, then relax edges repeatedly to find shortest paths, finally check for negative cycles.

Execution Sample

DSA Javascript

const edges = [
  {from: 'A', to: 'B', weight: 4},
  {from: 'A', to: 'C', weight: 2},
  {from: 'B', to: 'C', weight: -3},
  {from: 'C', to: 'D', weight: 2},
  {from: 'D', to: 'B', weight: 1}
];

const distances = {A: 0, B: Infinity, C: Infinity, D: Infinity};

// Relax edges V-1 times
for (let i = 0; i < 3; i++) {
  for (const edge of edges) {
    if (distances[edge.from] + edge.weight < distances[edge.to]) {
      distances[edge.to] = distances[edge.from] + edge.weight;
    }
  }
}

// Check for negative cycles
for (const edge of edges) {
  if (distances[edge.from] + edge.weight < distances[edge.to]) {
    console.log('Negative cycle detected');
  }
}

console.log(distances);

This code runs Bellman Ford on a graph with negative weights to find shortest paths or detect negative cycles.

Execution Table

Step	Operation	Edge Relaxed	Distances Before	Distances After	Visual State
1	Initialize distances	N/A	{}	{A:0, B:∞, C:∞, D:∞}	A(0) B(∞) C(∞) D(∞)
2	Relax edge	A->B (4)	{A:0, B:∞, C:∞, D:∞}	{A:0, B:4, C:∞, D:∞}	A(0) B(4) C(∞) D(∞)
3	Relax edge	A->C (2)	{A:0, B:4, C:∞, D:∞}	{A:0, B:4, C:2, D:∞}	A(0) B(4) C(2) D(∞)
4	Relax edge	B->C (-3)	{A:0, B:4, C:2, D:∞}	{A:0, B:4, C:1, D:∞}	A(0) B(4) C(1) D(∞)
5	Relax edge	C->D (2)	{A:0, B:4, C:1, D:∞}	{A:0, B:4, C:1, D:3}	A(0) B(4) C(1) D(3)
6	Relax edge	D->B (1)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
7	Relax edge	A->B (4)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
8	Relax edge	A->C (2)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
9	Relax edge	B->C (-3)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
10	Relax edge	C->D (2)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
11	Relax edge	D->B (1)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
12	Relax edge	A->B (4)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
13	Relax edge	A->C (2)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
14	Relax edge	B->C (-3)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
15	Relax edge	C->D (2)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
16	Relax edge	D->B (1)	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No change
17	Check negative cycle	All edges	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	No negative cycle detected

💡 After V-1=3 iterations, no edge can relax distances further, so shortest paths found and no negative cycle.

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
distances	{A:0, B:∞, C:∞, D:∞}	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}	{A:0, B:4, C:1, D:3}

Key Moments - 3 Insights

Why do we relax all edges V-1 times?

Because the longest possible path without cycles has V-1 edges, relaxing that many times ensures shortest paths are found (see execution_table rows 2-16).

What does it mean if distances change after V-1 iterations?

It means a negative weight cycle exists, because shortest paths should stabilize after V-1 relaxations (see execution_table row 17 check).

Why do some relaxations not change distances?

Because the current distances are already the shortest possible, so no update is needed (see execution_table rows 7-16).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the distance to node B after relaxing edge D->B?

A 2

B -1

C 4

D ∞

💡 Hint

Check the 'Distances After' column at step 6 in execution_table.

At which step does the algorithm detect no further changes in distances during relaxation?

A Step 6

B Step 7

C Step 2

D Step 17

💡 Hint

Look for the first step where 'No change' appears in the Visual State column.

If the edge B->C had weight -5 instead of -3, what would happen after the first iteration?

A Distance to C would be -3

B Distance to C would be -1

C Distance to C would be -1 or less

D Distance to C would remain ∞

💡 Hint

Check how relaxing B->C edge affects C's distance in execution_table rows 4 and 14.

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances (source=0, others=∞)
- Relax all edges V-1 times to update shortest paths
- If any edge can still relax, negative cycle exists
- Handles negative weights safely
- Time complexity: O(V*E)

Full Transcript

Bellman Ford algorithm finds shortest paths from a source node to all others even with negative edge weights. It starts by setting the source distance to zero and others to infinity. Then it relaxes all edges repeatedly V-1 times, where V is the number of vertices. Relaxing means updating the distance to a node if a shorter path is found through an edge. After these iterations, if any edge can still reduce a distance, it means a negative weight cycle exists. Otherwise, the distances represent shortest paths. This example shows step-by-step how distances update and stabilize, and how the algorithm detects no negative cycles.

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