Bellman Ford Algorithm Negative Weights in DSA C#

Mental Model

Bellman Ford finds shortest paths even when edges have negative weights by relaxing edges multiple times.

Analogy: Imagine sending messages through a network where some roads reduce your travel cost. You keep updating your best known routes until no better path is found or you detect a loop that keeps reducing cost forever.

Graph:
  (A)
  / \
-1   4
 /     \
(B)---3-->(C)
Edges have weights, some negative.

Dry Run Walkthrough

Input: Graph with vertices A, B, C and edges: A->B (-1), B->C (3), A->C (4). Start from A.

Goal: Find shortest distances from A to all nodes, handling negative edge A->B.

Step 1: Initialize distances: A=0, B=∞, C=∞

Distances: A=0, B=∞, C=∞

Why: Start with source distance zero and others unknown

Step 2: Relax edge A->B: update B from ∞ to 0 + (-1) = -1

Distances: A=0, B=-1, C=∞

Why: Found shorter path to B via A

Step 3: Relax edge B->C: update C from ∞ to -1 + 3 = 2

Distances: A=0, B=-1, C=2

Why: Found shorter path to C via B

Step 4: Relax edge A->C: current C=2, new path 0 + 4 = 4, no update

Distances: A=0, B=-1, C=2

Why: Current path to C is already shorter

Step 5: Repeat relaxation for all edges (second iteration), no distance changes

Distances: A=0, B=-1, C=2

Why: No further improvements, algorithm can stop

Result:

Distances: A=0, B=-1, C=2

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Edge {
    public int Src, Dest, Weight;
    public Edge(int s, int d, int w) { Src = s; Dest = d; Weight = w; }
}

class Graph {
    public int V;
    public List<Edge> Edges;
    public Graph(int vertices) {
        V = vertices;
        Edges = new List<Edge>();
    }
    public void AddEdge(int s, int d, int w) {
        Edges.Add(new Edge(s, d, w));
    }
    public void BellmanFord(int src) {
        int[] dist = new int[V];
        for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
        dist[src] = 0;

        // Relax edges V-1 times
        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;
                }
            }
        }

        // Check for negative weight cycle
        foreach (var edge in Edges) {
            if (dist[edge.Src] != int.MaxValue && dist[edge.Src] + edge.Weight < dist[edge.Dest]) {
                Console.WriteLine("Graph contains negative weight cycle");
                return;
            }
        }

        // Print distances
        for (int i = 0; i < V; i++) {
            Console.WriteLine($"Distance from {src} to {i} is {dist[i]}");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(3);
        g.AddEdge(0, 1, -1); // A->B
        g.AddEdge(1, 2, 3);  // B->C
        g.AddEdge(0, 2, 4);  // A->C
        g.BellmanFord(0);
    }
}

dist[src] = 0;

Set source distance to zero to start

for (int i = 1; i <= V - 1; i++) {

Repeat relaxation for V-1 iterations to propagate shortest paths

if (dist[edge.Src] != int.MaxValue && dist[edge.Src] + edge.Weight < dist[edge.Dest]) {

Check if current edge can improve destination distance

dist[edge.Dest] = dist[edge.Src] + edge.Weight;

Update destination distance with shorter path

foreach (var edge in Edges) { if (dist[edge.Src] != int.MaxValue && dist[edge.Src] + edge.Weight < dist[edge.Dest]) { Console.WriteLine("Graph contains negative weight cycle"); return; } }

Detect negative weight cycle if any edge can still relax

Console.WriteLine($"Distance from {src} to {i} is {dist[i]}");

Print final shortest distances from source

Output

Distance from 0 to 0 is 0

Distance from 0 to 1 is -1

Distance from 0 to 2 is 2

Complexity Analysis

Time: O(V * E) because we relax all edges V-1 times

Space: O(V) for storing distances to each vertex

vs Alternative: Unlike Dijkstra which fails on negative weights, Bellman Ford handles them but is slower due to repeated edge relaxation

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and reports it instead of incorrect distances

DSA C#

foreach (var edge in Edges) { if (dist[edge.Src] != int.MaxValue && dist[edge.Src] + edge.Weight < dist[edge.Dest]) { Console.WriteLine("Graph contains negative weight cycle"); return; } }

Graph with no edges

Distances remain infinite except source which is zero

DSA C#

dist[src] = 0;

Single vertex graph

Distance to itself is zero, no edges to relax

DSA C#

dist[src] = 0;

When to Use This Pattern

When you see shortest path problems with possible negative edge weights, reach for Bellman Ford because it correctly handles negative weights and detects negative cycles.

Common Mistakes

Mistake: Using Dijkstra's algorithm on graphs with negative weights
Fix: Use Bellman Ford algorithm instead as it supports negative weights

Mistake: Not checking for negative weight cycles after relaxation
Fix: Add a final check to detect if any edge can still relax distances

Summary

Finds shortest paths from a source even with negative edge weights.

Use when graph edges can have negative weights and you need to detect negative cycles.

Relax all edges V-1 times to propagate shortest distances and detect cycles.

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