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.