Bellman Ford Algorithm Negative Weights in DSA Java - Execution Trace

Concept Flow - Bellman Ford Algorithm Negative Weights

Initialize distances

↓

Repeat V-1 times: Relax all edges

↓

For each edge: if distance can be improved, update it

↓

Check for negative weight cycles

↓

If found: report negative cycle

↓

Else: shortest distances finalized

The algorithm initializes distances, relaxes edges repeatedly, then checks for negative cycles.

Execution Sample

DSA Java

int V = 5;
int[] dist = new int[V];
for (int i = 1; i < V; i++) dist[i] = Integer.MAX_VALUE;
for (int i = 1; i <= V - 1; i++) {
  for (Edge e : edges) relax(e); }

This code initializes distances and relaxes all edges V-1 times to find shortest paths.

Execution Table

Step	Operation	Edge Relaxed	Distance Updated	Distance Array State	Visual State
0	Initialize distances	N/A	dist[0]=0, others=∞	[0, ∞, ∞, ∞, ∞]	0 -> ∞ -> ∞ -> ∞ -> ∞
1	Relax edge	(0->1, 6)	dist[1]=6	[0, 6, ∞, ∞, ∞]	0 -> 6 -> ∞ -> ∞ -> ∞
2	Relax edge	(0->2, 7)	dist[2]=7	[0, 6, 7, ∞, ∞]	0 -> 6 -> 7 -> ∞ -> ∞
3	Relax edge	(1->2, 8)	No update	[0, 6, 7, ∞, ∞]	0 -> 6 -> 7 -> ∞ -> ∞
4	Relax edge	(1->3, 5)	dist[3]=11	[0, 6, 7, 11, ∞]	0 -> 6 -> 7 -> 11 -> ∞
5	Relax edge	(1->4, -4)	dist[4]=2	[0, 6, 7, 11, 2]	0 -> 6 -> 7 -> 11 -> 2
6	Relax edge	(2->3, -3)	dist[3]=4	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
7	Relax edge	(2->4, 9)	No update	[0, 6, 7, 4, 2]	0 -> 6 -> 7 -> 4 -> 2
8	Relax edge	(3->1, -2)	dist[1]=2	[0, 2, 7, 4, 2]	0 -> 2 -> 7 -> 4 -> 2
9	Relax edge	(4->0, 2)	No update	[0, 2, 7, 4, 2]	0 -> 2 -> 7 -> 4 -> 2
10	Relax edge	(4->3, 7)	No update	[0, 2, 7, 4, 2]	0 -> 2 -> 7 -> 4 -> 2
11	Repeat relaxation cycle 2	All edges	dist[4]=-2	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2
12	Repeat relaxation cycle 3	All edges	No updates	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2
13	Repeat relaxation cycle 4	All edges	No updates	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2
14	Check for negative cycle	All edges	No updates	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2
15	End	N/A	Distances finalized	[0, 2, 7, 4, -2]	0 -> 2 -> 7 -> 4 -> -2

💡 No distance updates in last relaxation cycle, so algorithm stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 6	After Step 8	Final
dist	[0, ∞, ∞, ∞, ∞]	[0, 6, ∞, ∞, ∞]	[0, 6, 7, ∞, ∞]	[0, 6, 7, 11, 2]	[0, 6, 7, 4, 2]	[0, 2, 7, 4, 2]	[0, 2, 7, 4, -2]

Key Moments - 3 Insights

Why do we relax edges V-1 times?

Because the longest possible path without cycles has V-1 edges, so relaxing that many times ensures shortest paths are found (see steps 1-13 in execution_table).

Why do some edges not update distances during relaxation?

If the current distance is already shorter or equal, no update happens (see steps 3,7,9,10 where 'No update' occurs).

How does the algorithm detect negative weight cycles?

After V-1 relaxations, if any edge can still reduce distance, a negative cycle exists (step 14 shows no updates, so no negative cycle).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the distance to vertex 1?

A 2

B 6

C 4

D ∞

💡 Hint

Check the 'Distance Array State' column at step 8 in execution_table.

At which step does the distance to vertex 3 first update to 4?

A Step 5

B Step 6

C Step 4

D Step 8

💡 Hint

Look for 'dist[3]=4' update in the 'Distance Updated' column in execution_table.

If the edge (4->0) had weight -10 instead of 2, what would happen in the last relaxation cycle?

A No change, distances remain same

B Distance to vertex 4 would increase

C Distance to vertex 0 would decrease, indicating a negative cycle

D Algorithm would stop earlier

💡 Hint

Negative weight edges that reduce distances after V-1 relaxations indicate negative cycles (see step 14).

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances (start=0, others=∞)
- Relax all edges V-1 times
- Update distances if shorter path found
- Check for negative cycles by one more relaxation
- If no updates, shortest paths found
- Detect negative cycles if updates still possible

Full Transcript

Bellman Ford algorithm finds shortest paths from a start vertex even with negative weights. It initializes distances with zero for start and infinity for others. Then it relaxes all edges repeatedly V-1 times, updating distances if a shorter path is found. After these relaxations, it checks for negative weight cycles by trying to relax edges once more. If any distance updates, a negative cycle exists. Otherwise, the shortest distances are finalized. This example shows step-by-step how distances update and stabilize, and how the algorithm detects no negative cycles.

Practice

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

easy

A. It can handle graphs with negative weight edges.

B. It runs faster on all graphs.

C. It uses less memory.

D. It only works on directed acyclic graphs.

Solution

1. Step 1: Understand Dijkstra's limitation

   Dijkstra's algorithm cannot handle negative weight edges correctly because it assumes once a node is visited, its shortest path is finalized.

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 A

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 only works on acyclic graphs
• Confusing memory usage advantages

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

easy

A. int[] dist = new int[V]; Arrays.fill(dist, -1); dist[src] = 0;

B. int[] dist = new int[V]; dist[src] = Integer.MAX_VALUE;

C. int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;

D. int[] dist = new int[V]; Arrays.fill(dist, 0);

Solution

1. Step 1: Initialize distances to max value

   We set all distances to Integer.MAX_VALUE to represent infinity initially.

2. Step 2: Set source distance to zero

   The source vertex distance is set to 0 because distance from source to itself is zero.

3. Final Answer:

   int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; -> Option C

4. Quick Check:

   Distance init with max + source zero = D [OK]

Hint: Initialize all distances to max, source to zero [OK]

Common Mistakes:

• Setting source distance to max instead of zero
• Filling distances with zero instead of max
• Using -1 which is invalid for distances

3. Consider the following graph edges and weights:

int[][] edges = {
  {0, 1, 4},
  {0, 2, 5},
  {1, 2, -3},
  {2, 3, 4}
};
int V = 4; int src = 0;

What is the shortest distance array after running Bellman-Ford from source 0?

medium

A. [0, 4, 5, 9]

B. [0, 4, 1, 5]

C. [0, 4, 1, 9]

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

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF]

2. Step 2: Relax edges V-1 times

   Iteration 1: - Edge 0->1: dist[1] = min(INF, 0+4) = 4 - Edge 0->2: dist[2] = min(INF, 0+5) = 5 - Edge 1->2: dist[2] = min(5, 4-3) = 1 - Edge 2->3: dist[3] = min(INF, 1+4) = 5 Iteration 2 and 3 do not improve distances further.

3. Final Answer:

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

4. Quick Check:

   Relax edges 3 times, final dist = [0,4,1,5] [OK]

Hint: Relax edges V-1 times, update distances each time [OK]

Common Mistakes:

• Not updating dist[2] after edge 1->2 relaxation
• Ignoring negative edge effect
• Stopping after first iteration

4. Given this snippet of Bellman-Ford code, what is the error?

for (int i = 0; i < V; i++) {
  for (int[] edge : edges) {
    int u = edge[0], v = edge[1], w = edge[2];
    if (dist[u] != Integer.MAX_VALUE && 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 condition dist[u] != Integer.MAX_VALUE is incorrect.

C. The edge array indexing is wrong.

D. The distance update should be dist[u] - w instead of dist[u] + w.

Solution

1. Step 1: Check loop iteration count

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

2. Step 2: Identify loop error

   The code runs the outer loop V times, which is one extra iteration and can cause incorrect behavior 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: Run outer loop V-1 times for correct relaxation [OK]

Common Mistakes:

• Running loop V times instead of V-1
• Misunderstanding distance initialization condition
• Incorrect edge array indexing

5. You run Bellman-Ford on a graph with edges:

int[][] edges = {
  {0, 1, 1},
  {1, 2, -1},
  {2, 3, -1},
  {3, 1, -1}
};
int V = 4; int src = 0;

What will the algorithm detect after V-1 iterations?

hard

A. Algorithm will throw an exception due to negative weights.

B. No negative weight cycle; shortest paths found.

C. Distances will all be zero.

D. A negative weight cycle exists reachable from the source.

Solution

1. Step 1: Identify cycle in graph

   Edges 1->2, 2->3, 3->1 form a cycle with total weight -3 (negative).

2. Step 2: Bellman-Ford detects negative cycles

   After V-1 iterations, the algorithm checks for further relaxation. If possible, it means a negative weight cycle exists reachable from source.

3. Final Answer:

   A negative weight cycle exists reachable from the source. -> Option D

4. Quick Check:

   Negative cycle detected = C [OK]

Hint: Check for extra relaxation after V-1 iterations to find negative cycles [OK]

Common Mistakes:

• Assuming no negative cycle despite cycle with negative sum
• Expecting exception on negative weights
• Thinking distances become zero automatically