Why Bellman Ford Algorithm Negative Weights in DSA C#?

The Big Idea

What if some roads pay you to travel them? How do you find the cheapest path then?

The Scenario

Imagine you are planning a road trip across many cities. Some roads have tolls, and some roads even give you money back as discounts (negative costs). You try to find the cheapest path by listing all possible routes and adding up their costs manually.

The Problem

Manually checking every possible route is slow and confusing. When roads have discounts (negative weights), simple methods like always picking the next cheapest road can get stuck or give wrong answers. It's easy to miss cheaper paths or get lost in loops.

The Solution

The Bellman-Ford algorithm smartly checks all roads multiple times to find the cheapest path, even if some roads give discounts (negative weights). It can also detect if there is a loop that keeps reducing the cost forever (negative cycle), which manual methods can't handle well.

Before vs After

✗ Before

int[] costs = new int[numberOfCities];
// Manually add costs for each path
// Try to find cheapest path by guessing

✓ After

int[] costs = BellmanFord(graph, startCity);
// Automatically finds shortest paths even with negative weights

What It Enables

You can reliably find the cheapest routes in maps or networks that have discounts or penalties, and detect impossible situations caused by negative cycles.

Real Life Example

In finance, Bellman-Ford helps find the best currency exchange path when some exchanges offer bonuses (negative costs), ensuring you don't get stuck in endless profit loops.

Key Takeaways

Manual route checking fails with negative costs and loops.

Bellman-Ford handles negative weights and detects negative cycles.

It ensures correct shortest paths in complex weighted graphs.

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