Bellman Ford Algorithm Negative Weights in DSA Go - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances

↓

Repeat V-1 times: Relax all edges

↓

Check for negative weight cycles

↓

If found: Report negative cycle

↓

Else: Distances finalized

The algorithm starts by setting distances, then relaxes edges repeatedly, and finally checks for negative cycles.

Execution Sample

DSA Go

edges := []Edge{{0,1,4},{0,2,5},{1,2,-3},{2,3,4},{3,1,-6}}
V := 4
dist := make([]int, V)
for i := range dist { dist[i] = 1<<31 - 1 }
dist[0] = 0
for i := 0; i < V-1; i++ {
  for _, e := range edges { if dist[e.from] + e.weight < dist[e.to] { dist[e.to] = dist[e.from] + e.weight } } }

This code initializes distances and relaxes edges to find shortest paths, handling negative weights.

Execution Table

Step	Operation	Edge Relaxed	Distance Update	Distance Array	Notes
0	Initialize distances	-	dist[0]=0, others=∞	[0, ∞, ∞, ∞]	Start with source distance 0
1	Relax edges iteration 1	Edge(0->1,4)	dist[1]=0+4=4	[0,4,∞,∞]	Updated dist[1]
2	Relax edges iteration 1	Edge(0->2,5)	dist[2]=0+5=5	[0,4,5,∞]	Updated dist[2]
3	Relax edges iteration 1	Edge(1->2,-3)	dist[2]=4-3=1	[0,4,1,∞]	Improved dist[2]
4	Relax edges iteration 1	Edge(2->3,4)	dist[3]=1+4=5	[0,4,1,5]	Updated dist[3]
5	Relax edges iteration 1	Edge(3->1,-6)	dist[1]=5-6=-1	[0,-1,1,5]	Improved dist[1]
6	Relax edges iteration 2	Edge(0->1,4)	No update	[0,-1,1,5]	No change
7	Relax edges iteration 2	Edge(0->2,5)	No update	[0,-1,1,5]	No change
8	Relax edges iteration 2	Edge(1->2,-3)	dist[2]=-1-3=-4	[0,-1,-4,5]	Improved dist[2]
9	Relax edges iteration 2	Edge(2->3,4)	dist[3]=-4+4=0	[0,-1,-4,0]	Improved dist[3]
10	Relax edges iteration 2	Edge(3->1,-6)	dist[1]=0-6=-6	[0,-6,-4,0]	Improved dist[1]
11	Relax edges iteration 3	Edge(0->1,4)	No update	[0,-6,-4,0]	No change
12	Relax edges iteration 3	Edge(0->2,5)	No update	[0,-6,-4,0]	No change
13	Relax edges iteration 3	Edge(1->2,-3)	dist[2]=-6-3=-9	[0,-6,-9,0]	Improved dist[2]
14	Relax edges iteration 3	Edge(2->3,4)	dist[3]=-9+4=-5	[0,-6,-9,-5]	Improved dist[3]
15	Relax edges iteration 3	Edge(3->1,-6)	dist[1]=-5-6=-11	[0,-11,-9,-5]	Improved dist[1]
16	Check negative cycle	Edge(1->2,-3)	dist[2] can be improved	[0,-11,-9,-5]	Negative cycle detected
17	Stop	-	-	-	Algorithm stops due to negative cycle

💡 Negative cycle detected at step 16, algorithm stops to avoid infinite updates

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
dist	[∞, ∞, ∞, ∞]	[0,4,1,5]	[0,-6,-4,0]	[0,-11,-9,-5]	[0,-11,-9,-5]
iteration	0	1	2	3	3
edge	-	Edge(3->1,-6)	Edge(3->1,-6)	Edge(3->1,-6)	-

Key Moments - 3 Insights

Why does the distance to node 1 keep decreasing even after multiple iterations?

Because of the negative weight cycle detected at step 16, the distances keep improving infinitely, which is why the algorithm stops.

Why do we run the relaxation step V-1 times?

Because the longest possible path without cycles in a graph with V vertices has V-1 edges, so relaxing edges V-1 times ensures shortest paths are found if no negative cycles exist.

What happens if a distance does not update during an iteration?

It means no shorter path was found through any edge in that iteration, as seen in steps 6 and 7 where no updates occur.

Visual Quiz - 3 Questions

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

A 1

B -9

C -4

D 5

💡 Hint

Check the Distance Array column at step 10 in the execution table.

At which step does the algorithm detect a negative weight cycle?

A Step 16

B Step 15

C Step 14

D Step 17

💡 Hint

Look for the row mentioning 'Negative cycle detected' in the Notes column.

If the edge (3->1) had weight 2 instead of -6, what would happen to the distance to node 1 after iteration 3?

A -11

B No change from previous iteration

C -6

D 4

💡 Hint

Consider how a positive weight on edge (3->1) affects distance updates compared to negative weight in the variable_tracker.

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances with ∞ except source=0
- Relax all edges V-1 times
- Check for negative weight cycles
- If cycle found, report and stop
- Handles graphs with negative weights safely

Full Transcript

The Bellman Ford algorithm starts by setting the distance to the source node as zero and all others as infinity. It then relaxes all edges repeatedly for V-1 iterations, 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, the algorithm checks for negative weight cycles by trying to relax edges once more. If any distance improves, it means a negative cycle exists, and the algorithm stops to avoid infinite loops. This example shows distances updating step-by-step, including improvements due to negative edges and detection of a negative cycle.

Practice

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

easy

A. It runs faster on all graphs.

B. It uses less memory.

C. It can handle graphs with negative weight edges.

D. It only works on directed acyclic graphs.

Solution

1. Step 1: Understand Dijkstra's limitation

   Dijkstra's algorithm cannot handle negative weight edges because it assumes once a node is visited with the shortest path, it won't be updated again.

2. Step 2: Bellman-Ford's capability

   Bellman-Ford algorithm relaxes edges multiple times and can detect negative weight edges, allowing it to work correctly even with negative weights.

3. Final Answer:

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

4. Quick Check:

   Negative weights handled = B [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 than Dijkstra
• Assuming it only works on acyclic graphs

2. Which of the following is the correct way to initialize the distance array in the Bellman-Ford algorithm in Go?

easy

A. dist := make([]int, V); for i := range dist { dist[i] = math.MaxInt32 }

B. dist := make([]int, V); for i := range dist { dist[i] = 0 }

C. dist := make([]int, V); for i := range dist { dist[i] = -1 }

D. dist := make([]int, V); for i := range dist { dist[i] = 1 }

Solution

1. Step 1: Understand distance initialization

   Distances to all vertices except the source should be set to a very large number (infinity) to represent unknown distance.

2. Step 2: Use math.MaxInt32 for infinity

   In Go, math.MaxInt32 is used to represent a large integer value for initialization.

3. Final Answer:

   dist := make([]int, V); for i := range dist { dist[i] = math.MaxInt32 } -> Option A

4. Quick Check:

   Initialize distances to max int = A [OK]

Hint: Initialize distances to max int except source [OK]

Common Mistakes:

• Initializing distances to zero
• Using negative values for distances
• Not initializing distances at all

3. What will be the output distances array after running Bellman-Ford on this graph with edges:
edges = []Edge{{0,1,4}, {0,2,5}, {1,2,-3}, {2,3,4}} starting from source 0?

medium

A. [0, 4, 5, 9]

B. [0, 4, 1, 5]

C. [0, 4, 1, 9]

D. [0, 4, -3, 4]

Solution

1. Step 1: Initialize distances

   dist = [0, ∞, ∞, ∞]

2. Step 2: Relax edges repeatedly

   After first relaxation: dist[1]=4, dist[2]=5
   After second relaxation: dist[2]=min(5,4 + (-3))=1
   After third relaxation: dist[3]=dist[2] + 4 = 1 + 4 = 5
   After further relaxations no changes occur.

3. Final Answer:

   [0, 4, 1, 5] -> Option B

4. Quick Check:

   Relax edges stepwise = A [OK]

Hint: Relax edges V-1 times to update distances [OK]

Common Mistakes:

• Not updating dist[2] after negative edge relaxation
• Adding weights incorrectly
• Confusing edge directions

4. Identify the bug in this Go code snippet for Bellman-Ford algorithm:

for i := 0; i < V; i++ {
  for _, e := range edges {
    if dist[e.src] + e.weight < dist[e.dest] {
      dist[e.dest] = dist[e.src] + e.weight
    }
  }
}

medium

A. Loop should run V-1 times, not V times.

B. The condition should use <= instead of <.

C. dist array is not initialized.

D. Edges should be relaxed only once.

Solution

1. Step 1: Check loop iteration count

   Bellman-Ford requires relaxing edges exactly V-1 times to find shortest paths correctly.

2. Step 2: Identify off-by-one error

   The loop runs V times, which is one extra iteration and may cause incorrect behavior or unnecessary work.

3. Final Answer:

   Loop should run V-1 times, not V times. -> Option A

4. Quick Check:

   Relax edges V-1 times = A [OK]

Hint: Relax edges exactly V-1 times [OK]

Common Mistakes:

• Running loop V times instead of V-1
• Using wrong comparison operator
• Not initializing dist array

5. Given a graph with edges:
edges = []Edge{{0,1,1}, {1,2,-1}, {2,3,-1}, {3,1,-1}}
and source vertex 0, what does Bellman-Ford detect after running?

hard

A. No negative cycle detected; shortest paths found.

B. Distances remain infinite for all vertices except source.

C. Algorithm fails due to zero-weight edges.

D. Negative weight cycle detected involving vertices 1, 2, 3.

Solution

1. Step 1: Analyze edges for cycles

   The edges form a cycle 1 -> 2 -> 3 -> 1 with total weight -3 (negative cycle).

2. Step 2: Bellman-Ford cycle detection

   After V-1 relaxations, one more relaxation detects if any distance can still be reduced, indicating a negative cycle.

3. Final Answer:

   Negative weight cycle detected involving vertices 1, 2, 3. -> Option D

4. Quick Check:

   Negative cycle detection = D [OK]

Hint: Check for distance updates after V-1 relaxations [OK]

Common Mistakes:

• Ignoring negative cycles
• Assuming zero-weight edges cause failure
• Thinking no cycle exists