Bellman Ford Algorithm Negative Weights in DSA C++ - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances

↓

Repeat V-1 times

↓

For each edge

↓

Relax edge if possible

↓

Check for negative cycle

↓

Report distances or negative cycle

Start with distances, relax edges repeatedly, then check for negative cycles.

Execution Sample

DSA C++

int V = 5;
struct Edge { int u, v, w; };
vector<Edge> edges = {{0,1,6},{0,2,7},{1,2,8},{1,3,5},{1,4,-4},{2,3,-3},{2,4,9},{3,1,-2},{4,0,2},{4,3,7}};
vector<int> dist(V, INT_MAX);
dist[0] = 0;
for (int i=1; i<=V-1; i++) {
  for (auto &e : edges) {
    if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v])
      dist[e.v] = dist[e.u] + e.w;
  }
}

This code runs Bellman-Ford to find shortest paths from node 0 with negative weights.

Execution Table

Step	Operation	Edge Relaxed	Distance Updates	Distances State	Visual State
0	Initialize distances	None	dist[0]=0	[0, ∞, ∞, ∞, ∞]	0 -> ∞ -> ∞ -> ∞ -> ∞
1.1	Relax edge	(0->1,6)	dist[1]=6	[0, 6, ∞, ∞, ∞]	0 -> 6 -> ∞ -> ∞ -> ∞
1.2	Relax edge	(0->2,7)	dist[2]=7	[0, 6, 7, ∞, ∞]	0 -> 6 -> 7 -> ∞ -> ∞
1.3	Relax edge	(1->2,8)	No update	[0, 6, 7, ∞, ∞]	0 -> 6 -> 7 -> ∞ -> ∞
1.4	Relax edge	(1->3,5)	dist[3]=11	[0, 6, 7, 11, ∞]	0 -> 6 -> 7 -> 11 -> ∞
1.5	Relax edge	(1->4,-4)	dist[4]=2	[0, 6, 7, 11, 2]	0 -> 6 -> 7 -> 11 -> 2
1.6	Relax edge	(2->3,-3)	dist[3]=4	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
1.7	Relax edge	(2->4,9)	No update	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
1.8	Relax edge	(3->1,-2)	dist[1]=4	[0, 4, 7, 4, 2]	0 -> 4 -> 7 -> 4 -> 2
1.9	Relax edge	(4->0,2)	No update	[0, 4, 7, 4, 2]	0 -> 4 -> 7 -> 4 -> 2
1.10	Relax edge	(4->3,7)	No update	[0, 4, 7, 4, 2]	0 -> 4 -> 7 -> 4 -> 2
2.1	Relax edge	(0->1,6)	dist[1]=6	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
2.2	Relax edge	(0->2,7)	No update	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
2.3	Relax edge	(1->2,8)	No update	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
2.4	Relax edge	(1->3,5)	No update	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
2.5	Relax edge	(1->4,-4)	dist[4]=-2	[0, 6, 7, 4, -2]	0 -> 6 -> 7 -> 4 -> -2
2.6	Relax edge	(2->3,-3)	No update	[0, 6, 7, 4, -2]	0 -> 6 -> 7 -> 4 -> -2
2.7	Relax edge	(2->4,9)	No update	[0, 6, 7, 4, -2]	0 -> 6 -> 7 -> 4 -> -2
2.8	Relax edge	(3->1,-2)	dist[1]=2	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2
2.9	Relax edge	(4->0,2)	No update	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2
2.10	Relax edge	(4->3,7)	No update	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2
Check	Negative cycle check	No edge relaxed	No update	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2

💡 No distance updated in last iteration, so no negative cycle detected.

Variable Tracker

Variable	Start	After 1	After 2	Final
dist	[∞, ∞, ∞, ∞, ∞]	[0, 4, 7, 4, 2]	[0, 2, 7, 4, -2]	[0, 2, 7, 4, -2]

Key Moments - 3 Insights

Why do distances update multiple times during the algorithm?

Because each edge relaxation can improve distances step-by-step, as shown in execution_table rows 1.1 to 1.10 where distances get better gradually.

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

Because the longest possible path without cycles has V-1 edges, so after V-1 iterations, all shortest paths are found if no negative cycle exists, as seen in the two full passes in execution_table.

How do we detect a negative weight cycle?

By checking if any edge can still be relaxed after V-1 iterations. If yes, a negative cycle exists. Here, the last check step shows no updates, so no negative cycle.

Visual Quiz - 3 Questions

Look at the execution_table at step 1.8, what is the distance to node 1?

A 4

B 6

C ∞

D 0

💡 Hint

Check the Distance Updates and Distances State columns at step 1.8.

At which iteration does the distance to node 3 first become 4?

A 1.4

B 1.6

C 2.4

D 1.10

💡 Hint

Look at the Distance Updates column and Distances State at steps 1.4 and 1.6.

If the edge (4->3,7) had weight -10 instead, what would happen in the last check step?

A No update, no negative cycle

B Distance to node 4 would increase

C Distance to node 3 would decrease, indicating a negative cycle

D Algorithm would stop early

💡 Hint

Consider how edge relaxation works and the negative cycle check step in execution_table.

Concept Snapshot

Bellman-Ford Algorithm:
- Initialize distances with ∞ except source=0
- Relax all edges V-1 times
- Update distances if shorter path found
- Check for negative cycles by one more relaxation
- Detects negative weights and cycles
- Output shortest distances or report cycle

Full Transcript

Bellman-Ford algorithm finds shortest paths from a source node even with negative edge weights. It starts by setting all distances to infinity except the source which is zero. Then it repeats relaxing all edges 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, it checks if any edge can still be relaxed. If yes, it means there is a negative weight cycle reachable from the source. Otherwise, the distances represent shortest paths. The execution table shows step-by-step how distances improve and how the algorithm detects no negative cycle in this example.

Practice

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

easy

A. It only works on directed acyclic graphs.

B. It runs faster on all graphs.

C. It uses less memory.

D. It can handle graphs with negative weight edges.

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 D

4. Quick Check:

   Negative weights handled = D [OK]

Hint: Bellman Ford works with negative edges, Dijkstra does not [OK]

Common Mistakes:

• Thinking Bellman Ford is always faster than Dijkstra
• Believing Bellman Ford cannot detect negative cycles
• Assuming Bellman Ford only works on acyclic graphs

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

easy

A. vector<int> dist(V, 0); dist[src] = INT_MAX;

B. vector<int> dist(V, INT_MAX); dist[src] = 0;

C. vector<int> dist(V, -1); dist[src] = 0;

D. vector<int> dist(V, INT_MIN); dist[src] = 0;

Solution

1. Step 1: Understand distance initialization

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

2. Step 2: Set source distance to zero

   The source vertex distance is zero because the distance from source to itself is zero.

3. Final Answer:

   vector<int> dist(V, INT_MAX); dist[src] = 0; -> Option B

4. Quick Check:

   Initialize with INT_MAX and source zero = B [OK]

Hint: Initialize all distances to INT_MAX except source zero [OK]

Common Mistakes:

• Setting all distances to zero
• Using INT_MIN which is incorrect for distances
• Not setting source distance to zero

3. Consider the following graph edges and weights:

Edges: (0->1, 4), (0->2, 5), (1->2, -3), (2->3, 4), (3->1, 6)

What is the shortest distance from vertex 0 to vertex 3 after running Bellman Ford?

medium

A. 5

B. 9

C. 6

D. 7

Solution

1. Step 1: Initialize distances

   dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞.

2. Step 2: Relax edges repeatedly

   After first iteration: dist[1]=4, dist[2]=5, dist[3]=∞.
   Relax (1->2): dist[2]=4 + (-3) = 1.
   Relax (2->3): dist[3]=1 + 4 = 5.
   Relax (3->1): dist[1]=min(4, 5 + 6=11) = 4.
   Second iteration: No further improvements.
   Final dist[3] = 5.

3. Step 3: Check for negative cycles

   No negative cycle detected.

4. Final Answer:

   5 -> Option A

5. Quick Check:

   Shortest path dist to 3 = 5 [OK]

Hint: Relax edges V-1 times, track minimum distances [OK]

Common Mistakes:

• Not updating distances after negative edge relaxation
• Confusing edge directions
• Stopping relaxation too early

4. The following C++ code snippet attempts to implement Bellman Ford but has a bug:

for (int i = 0; i < V; i++) {
  for (auto edge : edges) {
    if (dist[edge.u] + edge.w < dist[edge.v]) {
      dist[edge.v] = dist[edge.u] + edge.w;
    }
  }
}

What is the bug?

medium

A. The outer loop should run V-1 times, not V times.

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

C. The distance array is not initialized.

D. Edges should be relaxed in reverse order.

Solution

1. Step 1: Understand Bellman Ford iteration count

   Bellman Ford requires relaxing edges exactly V-1 times to find shortest paths without negative cycles.

2. Step 2: Identify the loop error

   The code runs the outer loop V times, which is one extra iteration and may cause incorrect detection of negative cycles or unnecessary work.

3. Final Answer:

   The outer loop should run V-1 times, not V times. -> Option A

4. Quick Check:

   Outer loop count = V-1 [OK]

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

Common Mistakes:

• Running outer loop V times instead of V-1
• Changing comparison operator incorrectly
• Ignoring distance initialization

5. Given a graph with edges:

(0->1, 1), (1->2, -1), (2->3, -1), (3->1, -1)

What will Bellman Ford detect when run from vertex 0?

hard

A. Graph is disconnected.

B. Shortest distances without any issues.

C. A negative weight cycle reachable from source.

D. Algorithm will run infinitely.

Solution

1. Step 1: Identify the cycle in the graph

   The edges (1->2), (2->3), and (3->1) form a cycle with total weight -1 + -1 + -1 = -3, which is negative.

2. Step 2: Understand Bellman Ford's negative cycle detection

   Bellman Ford detects negative weight cycles reachable from the source by checking if any edge can still be relaxed after V-1 iterations.

3. Step 3: Conclusion

   Since the negative cycle is reachable from vertex 0, Bellman Ford will detect it and report its presence.

4. Final Answer:

   A negative weight cycle reachable from source. -> Option C

5. Quick Check:

   Negative cycle detected = A [OK]

Hint: Negative cycle if edges relax after V-1 iterations [OK]

Common Mistakes:

• Ignoring negative cycles reachable from source
• Assuming algorithm runs infinitely
• Thinking graph is disconnected