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

↓

Check if distance to destination can be improved

Yes↓

Update distance

↓

After V-1 iterations

↓

Check for negative weight cycles

↓

Report negative cycle

↓

Shortest distances found

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

Execution Sample

DSA C#

int[] dist = new int[V];
for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
dist[src] = 0;
for (int i = 1; i <= V - 1; i++)
  foreach (var edge in edges)
    if (dist[edge.src] != int.MaxValue && dist[edge.src] + edge.weight < dist[edge.dest])
      dist[edge.dest] = dist[edge.src] + edge.weight;

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

Execution Table

Step	Operation	Edge Relaxed	Distance Update	Distances Array	Visual State
0	Initialize distances	N/A	dist[0] = 0; others = ∞	[0, ∞, ∞, ∞]	0 -> ∞ -> ∞ -> ∞
1	Relax edges iteration 1	(0->1, 4)	dist[1] = 0 + 4 = 4	[0, 4, ∞, ∞]	0 -> 4 -> ∞ -> ∞
2	Relax edges iteration 1	(0->2, 5)	dist[2] = 0 + 5 = 5	[0, 4, 5, ∞]	0 -> 4 -> 5 -> ∞
3	Relax edges iteration 1	(1->3, -10)	dist[3] = 4 + (-10) = -6	[0, 4, 5, -6]	0 -> 4 -> 5 -> -6
4	Relax edges iteration 2	(0->1, 4)	No update (4 ≤ 0+4)	[0, 4, 5, -6]	0 -> 4 -> 5 -> -6
5	Relax edges iteration 2	(0->2, 5)	No update (5 ≤ 0+5)	[0, 4, 5, -6]	0 -> 4 -> 5 -> -6
6	Relax edges iteration 2	(1->3, -10)	No update (-6 ≤ 4-10)	[0, 4, 5, -6]	0 -> 4 -> 5 -> -6
7	Relax edges iteration 3	(0->1, 4)	No update	[0, 4, 5, -6]	0 -> 4 -> 5 -> -6
8	Relax edges iteration 3	(0->2, 5)	No update	[0, 4, 5, -6]	0 -> 4 -> 5 -> -6
9	Relax edges iteration 3	(1->3, -10)	No update	[0, 4, 5, -6]	0 -> 4 -> 5 -> -6
10	Check negative cycle	(1->3, -10)	dist[3] > dist[1] + (-10)? -6 > 4 + (-10)? No	[0, 4, 5, -6]	No negative cycle detected

💡 No distance updated in last iteration, no negative cycle found, algorithm ends.

Variable Tracker

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

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-9 in execution_table).

What if a distance does not update in an iteration?

It means no shorter path was found in that iteration, so the algorithm is converging (see steps 4-9 where no updates happen).

How do we detect a negative weight cycle?

After V-1 relaxations, if any edge can still reduce a distance, a negative cycle exists (see step 10 checking edge 1->3).

Visual Quiz - 3 Questions

Look at the execution_table, what is the distance to node 3 after step 3?

A ∞

B -6

C 4

D 5

💡 Hint

Check the Distances Array column at step 3 in execution_table.

At which step does the algorithm confirm no negative cycle exists?

A Step 1

B Step 9

C Step 10

D Step 0

💡 Hint

Look at the operation 'Check negative cycle' in execution_table.

If edge (1->3) had weight -20 instead of -10, what would happen at step 3?

A dist[3] would update to -16

B dist[3] would update to -6

C No update to dist[3]

D dist[3] would become ∞

💡 Hint

Calculate dist[1] + new weight at step 3 and compare with current dist[3] in execution_table.

Concept Snapshot

Bellman Ford Algorithm:
- Initialize distances with ∞, source = 0
- Relax all edges V-1 times
- Update distances if shorter path found
- Check for negative cycles by one more relaxation
- If update possible, negative cycle exists
- Otherwise, shortest paths found

Full Transcript

The Bellman Ford algorithm starts by setting all node distances to infinity except the source node which is zero. It then relaxes all edges repeatedly for V-1 times, where V is the number of vertices. Relaxing means checking if the current known distance to a node can be improved by going through another node. After these iterations, the algorithm checks for negative weight cycles by trying to relax edges one more time. If any distance improves, a negative cycle exists. Otherwise, the shortest distances are finalized. This example shows distances updating step by step and no negative cycle detected.

Practice

1. What is the main purpose of the Bellman-Ford algorithm when dealing with graphs that have negative edge weights?

easy

A. To find the shortest path from a single source to all vertices, even with negative weights

B. To detect cycles in an undirected graph

C. To find the minimum spanning tree of a graph

D. To sort vertices in topological order

Solution

1. Step 1: Understand Bellman-Ford's capability

   The Bellman-Ford algorithm is designed to find shortest paths from a single source vertex to all other vertices in a graph, even if some edges have negative weights.

2. Step 2: Compare with other algorithms

   Unlike Dijkstra's algorithm, Bellman-Ford can handle negative weights and also detect negative weight cycles.

3. Final Answer:

   To find the shortest path from a single source to all vertices, even with negative weights -> Option A

4. Quick Check:

   Bellman-Ford finds shortest paths with negative weights [OK]

Hint: Bellman-Ford handles negative edges and finds shortest paths [OK]

Common Mistakes:

• Confusing Bellman-Ford with algorithms for minimum spanning trees
• Thinking it only detects cycles without finding paths
• Assuming it cannot handle negative weights

2. Which of the following is the correct C# syntax to initialize the distance array for Bellman-Ford with infinite values except the source vertex at index 0 set to 0?

easy

A. int[] dist = new int[n]; for(int i=0; i

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

C. int[] dist = new int[n]; dist.Fill(int.MaxValue); dist[0] = 0;

D. int[] dist = Enumerable.Repeat(int.MaxValue, n).ToArray(); dist[0] = 0;

Solution

1. Step 1: Understand array initialization with default values

   Using Enumerable.Repeat(int.MaxValue, n).ToArray() creates an array filled with int.MaxValue for all elements.

2. Step 2: Set source distance to zero

   After initialization, setting dist[0] = 0 correctly sets the source vertex distance.

3. Final Answer:

   int[] dist = Enumerable.Repeat(int.MaxValue, n).ToArray(); dist[0] = 0; -> Option D

4. Quick Check:

   Correct array initialization with source zero [OK]

Hint: Use Enumerable.Repeat for array filled with max values [OK]

Common Mistakes:

• Using dist.Fill which is not a valid method in C# arrays
• Setting dist[0] before initializing the array
• Not initializing all elements to int.MaxValue

3. Consider the following C# code snippet implementing one iteration of edge relaxation in Bellman-Ford. What will be the output distances array after this iteration?

int n = 4;
int[] dist = {0, int.MaxValue, int.MaxValue, int.MaxValue};
(int u, int v, int w)[] edges = {
  (0, 1, 1),
  (1, 2, -1),
  (2, 3, -1),
  (3, 1, -1)
};

foreach(var edge in edges) {
  if(dist[edge.u] != int.MaxValue && dist[edge.u] + edge.w < dist[edge.v]) {
    dist[edge.v] = dist[edge.u] + edge.w;
  }
}

Console.WriteLine(string.Join(", ", dist));

medium

A. 0, int.MaxValue, int.MaxValue, int.MaxValue

B. 0, 1, int.MaxValue, int.MaxValue

C. 0, -2, 0, -1

D. 0, 1, 0, -1

Solution

1. Step 1: Relax edge (0,1,1)

   dist[0] = 0, so dist[1] = min(int.MaxValue, 0+1) = 1

2. Step 2: Relax edge (1,2,-1)

   dist[1] = 1, so dist[2] = min(int.MaxValue, 1-1) = 0

3. Step 3: Relax edge (2,3,-1)

   dist[2] = 0, so dist[3] = min(int.MaxValue, 0-1) = -1

4. Step 4: Relax edge (3,1,-1)

   dist[3] = -1, so dist[1] = min(1, -1-1) = -2

5. Final Answer:

   0, -2, 0, -1 -> Option C

6. Quick Check:

   Distances updated correctly after one iteration [OK]

Hint: Relax edges in order, update distances if smaller [OK]

Common Mistakes:

• Not updating dist[1] after last edge relaxation
• Ignoring negative weights in relaxation
• Assuming no change if dist[v] is int.MaxValue

4. The following C# code snippet is intended to detect a negative weight cycle using Bellman-Ford. Identify the error:

bool HasNegativeCycle(int n, (int u, int v, int w)[] edges, int source) {
  int[] dist = Enumerable.Repeat(int.MaxValue, n).ToArray();
  dist[source] = 0;
  for(int i = 1; i <= n; i++) {
    foreach(var edge in edges) {
      if(dist[edge.u] != int.MaxValue && dist[edge.u] + edge.w < dist[edge.v]) {
        dist[edge.v] = dist[edge.u] + edge.w;
        if(i == n) return true;
      }
    }
  }
  return false;
}

medium

A. The loop should run from 1 to n-1, not 1 to n

B. The distance array should be initialized with zeros

C. The source vertex distance should be int.MaxValue, not 0

D. The return true should be outside the inner foreach loop

Solution

1. Step 1: Understand Bellman-Ford iteration count

   Bellman-Ford relaxes edges exactly n-1 times to find shortest paths without negative cycles.

2. Step 2: Detect negative cycle on nth iteration

   If any edge can still be relaxed on the nth iteration, a negative cycle exists.

3. Step 3: Identify loop range error

   The code runs the loop from 1 to n inclusive. Bellman-Ford should relax edges exactly n-1 times, then check separately on the nth iteration.

4. Final Answer:

   The loop should run from 1 to n-1, not 1 to n -> Option A

5. Quick Check:

   Relax edges n-1 times before checking cycle [OK]

Hint: Relax edges n-1 times, then check for cycle [OK]

Common Mistakes:

• Running relaxation loop n times instead of n-1
• Initializing distances incorrectly
• Returning true inside inner loop prematurely

5. You have a graph with 5 vertices and edges with some negative weights but no negative cycles. How many times must the Bellman-Ford algorithm relax all edges to guarantee correct shortest paths?

hard

A. 6 times

B. 4 times

C. 3 times

D. 5 times

Solution

1. Step 1: Recall Bellman-Ford relaxation count rule

   Bellman-Ford requires relaxing all edges exactly n-1 times, where n is the number of vertices.

2. Step 2: Apply to given graph

   For 5 vertices, the algorithm must relax edges 5-1 = 4 times to guarantee shortest paths.

3. Final Answer:

   4 times -> Option B

4. Quick Check:

   Relax edges n-1 times for n vertices [OK]

Hint: Relax edges n-1 times for n vertices [OK]

Common Mistakes:

• Relaxing edges n times instead of n-1
• Confusing number of edges with number of vertices
• Assuming negative weights require more iterations