Bellman Ford Algorithm Negative Weights in DSA Typescript - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances with Infinity except source=0

↓

Relax all edges

↓

Repeat relaxation V-1 times

↓

Check for negative weight cycles

↓

Report negative cycle

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

Execution Sample

DSA Typescript

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

This code runs Bellman Ford on a graph with 3 nodes and edges including a negative weight edge.

Execution Table

Step	Operation	Edge Relaxed	Distance Array Before	Distance Array After	Visual State
0	Initialize distances	N/A	[∞, ∞, ∞]	[0, ∞, ∞]	0:0, 1:∞, 2:∞
1	Relax edge	0->1 (4)	[0, ∞, ∞]	[0, 4, ∞]	0:0, 1:4, 2:∞
2	Relax edge	0->2 (5)	[0, 4, ∞]	[0, 4, 5]	0:0, 1:4, 2:5
3	Relax edge	1->2 (-3)	[0, 4, 5]	[0, 4, 1]	0:0, 1:4, 2:1
4	Relax edge	0->1 (4)	[0, 4, 1]	[0, 4, 1]	No change
5	Relax edge	0->2 (5)	[0, 4, 1]	[0, 4, 1]	No change
6	Relax edge	1->2 (-3)	[0, 4, 1]	[0, 4, 1]	No change
7	Check negative cycle	N/A	[0, 4, 1]	[0, 4, 1]	No negative cycle found
8	End	N/A	N/A	N/A	Distances finalized

💡 After V-1=2 relaxations, no distance updates; no negative cycle detected; algorithm ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	Final
dist	[∞, ∞, ∞]	[0, 4, ∞]	[0, 4, 5]	[0, 4, 1]	[0, 4, 1]	[0, 4, 1]
step	0	1	2	3	6	8

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, as shown in steps 1 to 6 where distances update until stable.

What happens if a distance does not change during relaxation?

If no distance updates occur during a full pass (like steps 4-6), it means shortest paths are found and further relaxations won't change distances.

How does the algorithm detect negative weight cycles?

After V-1 relaxations, if any edge can still relax a distance (not shown here), it means a negative cycle exists, as checked in step 7.

Visual Quiz - 3 Questions

Look at the execution table, what is the distance to node 2 after step 3?

A ∞

B 5

C 1

D 4

💡 Hint

Check the 'Distance Array After' column at step 3 in the execution table.

At which step does the algorithm confirm no negative weight cycle exists?

A Step 7

B Step 3

C Step 6

D Step 1

💡 Hint

Look for the 'Check negative cycle' operation in the execution table.

If the edge 1->2 had weight -5 instead of -3, what would happen at step 3?

A Distance to node 2 becomes 4

B Distance to node 2 becomes -1

C Distance to node 2 remains 5

D Distance to node 2 becomes 0

💡 Hint

Calculate new distance: dist[1] + weight = 4 + (-5) = -1, check step 3 logic.

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances: source=0, others=∞
- Relax all edges V-1 times
- Update distances if shorter path found
- Check for negative cycles by extra relaxation
- Detects shortest paths even with negative weights
- Stops if no changes or negative cycle found

Full Transcript

Bellman Ford algorithm starts by setting all distances to infinity except the source node which is zero. It then relaxes all edges repeatedly for V-1 times, where V is the number of vertices. Relaxing means checking if going through an edge improves the known shortest distance to a node. After these relaxations, the algorithm checks for negative weight cycles by trying to relax edges once more. If any distance improves, a negative cycle exists. Otherwise, the shortest distances are finalized. This example shows distances updating step-by-step and no negative cycle detected.

Practice

1. What is the main advantage of the Bellman-Ford algorithm compared to Dijkstra's algorithm?

easy

A. It uses less memory.

B. It runs faster on all graphs.

C. It can handle graphs with negative weight edges.

D. It only works on directed acyclic graphs.

Solution

1. Step 1: Understand the limitation of Dijkstra's algorithm

   Dijkstra's algorithm cannot correctly handle graphs with negative weight edges because it assumes that once a node's shortest path is found, it cannot be improved.

2. Step 2: Identify Bellman-Ford's capability

   Bellman-Ford algorithm can handle negative weight edges and detect negative weight cycles, making it more versatile for such graphs.

3. Final Answer:

   It can handle graphs with negative weight edges. -> Option C

4. Quick Check:

   Negative weights handled = A [OK]

Hint: Bellman-Ford works with negative edges, Dijkstra doesn't [OK]

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Believing it uses less memory
• Assuming it only works on acyclic graphs

2. Which of the following is the correct TypeScript syntax to initialize the distance array for Bellman-Ford with infinity except the source node set to 0?

easy

A. const dist = new Array(n).fill(Infinity); dist[source] = 0;

B. const dist = Array(n).fill(0); dist[source] = Infinity;

C. const dist = new Array(n).fill(0); dist[source] = 0;

D. const dist = new Array(n).fill(-Infinity); dist[source] = 0;

Solution

1. Step 1: Initialize distances with Infinity

   We start with all distances as Infinity to represent unknown paths, except the source which is 0.

2. Step 2: Correct syntax for array initialization

   Using new Array(n).fill(Infinity) creates an array of size n filled with Infinity, then setting dist[source] = 0 sets the source distance correctly.

3. Final Answer:

   const dist = new Array(n).fill(Infinity); dist[source] = 0; -> Option A

4. Quick Check:

   Initialize with Infinity except source 0 = C [OK]

Hint: Fill array with Infinity, then set source to 0 [OK]

Common Mistakes:

• Filling with 0 instead of Infinity
• Setting source distance to Infinity
• Using -Infinity which is incorrect

3. Consider the following TypeScript code snippet implementing one iteration of edge relaxation in Bellman-Ford:

for (const [u, v, w] of edges) {
  if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
  }
}
console.log(dist);

If edges = [[0,1,4],[1,2,-2],[0,2,5]] and initial dist = [0, Infinity, Infinity], what will be the output after this iteration?

medium

A. [0, 4, 5]

B. [0, 5, 3]

C. [0, Infinity, Infinity]

D. [0, 4, 2]

Solution

1. Step 1: Relax edge (0,1,4)

   dist[0] = 0, 0 + 4 = 4 < dist[1] (Infinity), so dist[1] = 4.

2. Step 2: Relax edge (1,2,-2)

   dist[1] = 4, 4 + (-2) = 2 < dist[2] (Infinity), so dist[2] = 2.

3. Step 3: Relax edge (0,2,5)

   dist[0] = 0, 0 + 5 = 5 < dist[2] (2)? No, so no update.

4. Final Answer:

   [0, 4, 2] -> Option D

5. Quick Check:

   Relax edges updates dist to [0,4,2] [OK]

Hint: Relax edges in order, update dist if smaller [OK]

Common Mistakes:

• Not updating dist[2] after second edge
• Updating dist[2] incorrectly on last edge
• Ignoring initial Infinity checks

4. The following TypeScript code attempts to detect a negative weight cycle after Bellman-Ford iterations:

for (const [u, v, w] of edges) {
  if (dist[u] + w < dist[v]) {
    console.log('Negative cycle detected');
  }
}

What is the bug in this code snippet?

medium

A. It does not check if dist[u] is Infinity before comparison.

B. It should update dist[v] inside the loop.

C. It should use <= instead of < in the condition.

D. It should run inside the main relaxation loop.

Solution

1. Step 1: Understand the condition for negative cycle detection

   After all relaxation rounds, if any edge can still relax dist[v], a negative cycle exists.

2. Step 2: Identify missing Infinity check

   If dist[u] is Infinity (unreachable), dist[u] + w is invalid and can cause wrong detection or runtime error.

3. Final Answer:

   It does not check if dist[u] is Infinity before comparison. -> Option A

4. Quick Check:

   Check dist[u] !== Infinity before comparing [OK]

Hint: Always check dist[u] !== Infinity before edge relaxation [OK]

Common Mistakes:

• Forgetting to check dist[u] Infinity
• Trying to update dist[v] in detection phase
• Misplacing detection inside main loop

5. You have a graph with edges: [[0,1,1],[1,2,-1],[2,3,-1],[3,1,-1]]. Using Bellman-Ford from source 0, what will be the result after all iterations?

hard

A. Algorithm will run infinitely without detection.

B. Negative cycle detected because the cycle 1->2->3->1 sums to -3.

C. Shortest distances: [0, 1, 2, 3]

D. Shortest distances: [0, 1, 0, -1]

Solution

1. Step 1: Identify the cycle and its weight

   The cycle 1->2->3->1 has weights 1->2 (-1), 2->3 (-1), 3->1 (-1), total -3, which is negative.

2. Step 2: Bellman-Ford detects negative cycles

   After |V|-1 iterations, if any edge can still relax distances, it means a negative cycle exists.

3. Step 3: Result of running Bellman-Ford

   The algorithm will detect the negative cycle and report it instead of giving shortest distances.

4. Final Answer:

   Negative cycle detected because the cycle 1->2->3->1 sums to -3. -> Option B

5. Quick Check:

   Negative cycle sum < 0 means detection = D [OK]

Hint: Sum cycle weights; negative sum means cycle detected [OK]

Common Mistakes:

• Ignoring negative cycle and reporting distances
• Assuming algorithm runs infinitely
• Miscomputing cycle weight