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 cycles

↓

Report shortest paths or negative cycle

Start with distances, relax all edges V-1 times, then check for negative cycles.

Execution Sample

DSA C

int dist[V];
for (int i = 0; i < V; i++) dist[i] = INF;
dist[src] = 0;
for (int i = 1; i <= V-1; i++) {
  for (each edge u->v with weight w) {
    if (dist[u] != INF && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  }
}

Initialize distances and relax all edges V-1 times to find shortest paths.

Execution Table

Step	Operation	Edge Relaxed	Distance Update	Distances State	Notes
0	Initialize distances	-	-	[0, INF, INF, INF]	Set source distance to 0, others to infinity
1.1	Relax edge	0->1 (weight 4)	dist[1] = 0 + 4 = 4	[0, 4, INF, INF]	First relaxation
1.2	Relax edge	0->2 (weight 5)	dist[2] = 0 + 5 = 5	[0, 4, 5, INF]	Relax next edge
1.3	Relax edge	1->2 (weight -3)	dist[2] = 4 + (-3) = 1	[0, 4, 1, INF]	Improved distance to node 2
1.4	Relax edge	2->3 (weight 2)	dist[3] = 1 + 2 = 3	[0, 4, 1, 3]	Distance to node 3 updated
2.1	Relax edge	0->1 (weight 4)	No update	[0, 4, 1, 3]	No improvement
2.2	Relax edge	0->2 (weight 5)	No update	[0, 4, 1, 3]	No improvement
2.3	Relax edge	1->2 (weight -3)	No update	[0, 4, 1, 3]	No improvement
2.4	Relax edge	2->3 (weight 2)	No update	[0, 4, 1, 3]	No improvement
3.1	Relax edge	0->1 (weight 4)	No update	[0, 4, 1, 3]	No improvement
3.2	Relax edge	0->2 (weight 5)	No update	[0, 4, 1, 3]	No improvement
3.3	Relax edge	1->2 (weight -3)	No update	[0, 4, 1, 3]	No improvement
3.4	Relax edge	2->3 (weight 2)	No update	[0, 4, 1, 3]	No improvement
Check	Negative cycle check	All edges	No update	[0, 4, 1, 3]	No negative cycle detected

💡 After V-1=3 iterations, no further distance updates; algorithm ends.

Variable Tracker

Variable	Start	After 1.1	After 1.2	After 1.3	After 1.4	After 2.4	After 3.4	Final
dist	[0, INF, INF, INF]	[0, 4, INF, INF]	[0, 4, 5, INF]	[0, 4, 1, INF]	[0, 4, 1, 3]	[0, 4, 1, 3]	[0, 4, 1, 3]	[0, 4, 1, 3]

Key Moments - 3 Insights

Why do we relax 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 1.x to 3.x).

What if distances do not update in an iteration?

If no distances update during an iteration (see iteration 2 and 3 in execution_table), it means shortest paths are found early and further relaxations won't change distances.

How does the algorithm detect negative weight cycles?

After V-1 relaxations, if any edge can still be relaxed (distance improved), it means a negative cycle exists (see 'Check' step in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 1.3, what is the distance to node 2?

A 1

B 4

C 5

D INF

💡 Hint

Check the 'Distance Update' and 'Distances State' columns at step 1.3.

At which iteration does the algorithm stop updating distances?

A After iteration 3

B After iteration 1

C After iteration 2

D Never stops

💡 Hint

Look at the 'Distance Update' column in iterations 2 and 3 in execution_table.

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

A dist[2] would not change

B dist[2] would become -1

C dist[2] would become 1

D dist[2] would become 4

💡 Hint

Calculate dist[1] + new weight: 4 + (-5) = -1, compare with current dist[2].

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances with INF, source = 0
- Relax all edges V-1 times
- Update dist[v] if dist[u] + w < dist[v]
- Detect negative cycles if relaxation possible after V-1 iterations
- Handles negative weights safely

Full Transcript

Bellman Ford algorithm finds shortest paths from a source node to all others even with negative weights. It starts by setting all distances to infinity except the source which is zero. Then it repeats relaxing all edges V-1 times, updating distances if a shorter path is found. If after these iterations any edge can still be relaxed, it means a negative weight cycle exists. The execution table shows step-by-step how distances update or stay the same. Key moments clarify why V-1 iterations are needed, what no updates mean, and how negative cycles are detected. The visual quiz tests understanding of distance updates and cycle detection.

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: Recognize Bellman-Ford's capability

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

3. Final Answer:

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

4. Quick Check:

   Negative weights handled = A [OK]

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

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Assuming it uses less memory
• Believing it 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. int dist[V]; for(int i=0; i

B. int dist[V]; for(int i=0; i

C. int dist[V]; for(int i=0; i

D. int dist[V]; for(int i=0; i

Solution

1. Step 1: Understand distance initialization

   Distances to all vertices except the source should be set to a very large number (infinity), here represented by INT_MAX, to indicate they are initially unreachable.

2. Step 2: Set source distance to zero

   The distance to the source vertex itself must be zero because the shortest path from source to source is zero.

3. Final Answer:

   int dist[V]; for(int i=0; i -> Option B

4. Quick Check:

   Initialize all to max, source to 0 = C [OK]

Hint: Set all distances to INT_MAX except source = 0 [OK]

Common Mistakes:

• Initializing all distances to zero
• Using -1 for unreachable distances
• Setting all distances to source index

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

medium

A. [0, 4, 1, 5]

B. [0, 4, 1, 9]

C. [0, 4, 5, 9]

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

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF]

2. Step 2: Relax edges repeatedly

   First iteration:
   dist[1] = min(INF, 0+4) = 4
   dist[2] = min(INF, 0+5) = 5
   dist[2] = min(5, 4 + (-3)) = 1
   dist[3] = min(INF, 1 + 4) = 5
   Second iteration:
   dist[1] stays 4
   dist[2] stays 1
   dist[3] stays 5
   No further updates.

3. Final distances:

   [0, 4, 1, 5]

4. Final Answer:

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

5. Quick Check:

   Relax edges to update distances = A [OK]

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

Common Mistakes:

• Not relaxing edges enough times
• Ignoring negative edge effect
• Wrong initial distances

4. Identify the error in this Bellman-Ford code snippet in C:

for (int i = 0; i < V; i++) {
  for (int j = 0; j < E; j++) {
    int u = edges[j].src;
    int v = edges[j].dest;
    int w = edges[j].weight;
    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 run V times, not E times.

C. The distance array is not initialized.

D. The weight comparison should be dist[v] + w < dist[u].

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 the incorrect loop count

   The outer loop runs V times here, which is one extra iteration and unnecessary.

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 = D [OK]

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

Common Mistakes:

• Running outer loop V times instead of V-1
• Confusing inner loop count with vertex count
• Incorrect weight comparison direction

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 source 0?

hard

A. It will run infinitely without stopping.

B. It will find shortest paths without any issues.

C. It will detect a negative weight cycle.

D. It will give incorrect distances but no error.

Solution

1. Step 1: Analyze 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 by checking for further relaxation after V-1 iterations. Here, it will detect the negative cycle.

3. Final Answer:

   It will detect a negative weight cycle. -> Option C

4. Quick Check:

   Negative cycle detected = A [OK]

Hint: Negative cycle if distances keep decreasing after V-1 relaxations [OK]

Common Mistakes:

• Assuming algorithm runs infinitely
• Believing it finds shortest paths despite negative cycle
• Ignoring cycle detection step