Bellman Ford Algorithm Negative Weights in DSA C# - Build from Scratch

Bellman Ford Algorithm Negative Weights

📖 Scenario: You are working on a navigation system that needs to find the shortest paths from a starting city to all other cities. Some roads have toll discounts, which means the travel cost can be negative. You will use the Bellman Ford algorithm to handle these negative weights safely.

🎯 Goal: Build a program that uses the Bellman Ford algorithm to find the shortest distances from a starting city to all other cities in a graph that may have negative edge weights.

📋 What You'll Learn

Create a list of edges representing the graph with exact values

Create a variable for the number of vertices called verticesCount

Implement the Bellman Ford algorithm to update shortest distances

Print the shortest distances from the start vertex after running the algorithm

💡 Why This Matters

🌍 Real World

Navigation systems and routing algorithms often need to handle roads with discounts or penalties, which can be modeled as negative weights. Bellman Ford helps find shortest paths safely in such cases.

💼 Career

Understanding Bellman Ford is important for software engineers working on graph algorithms, network routing, and optimization problems where negative weights can occur.

1

Create the graph edges

Create a list of edges called edges with these exact entries: (0, 1, 6), (0, 2, 7), (1, 2, 8), (1, 3, 5), (1, 4, -4), (2, 3, -3), (2, 4, 9), (3, 1, -2), (4, 0, 2), (4, 3, 7). Use a class Edge with properties Source, Destination, and Weight.

DSA C#

using System;
using System.Collections.Generic;

class Edge
{
    public int Source, Destination, Weight;
    public Edge(int source, int destination, int weight)
    {
        Source = source;
        Destination = destination;
        Weight = weight;
    }
}

class Program
{
    static void Main()
    {
        // Create the list of edges
        // Your code here
    }
}

Hint

Use List<Edge> and add new Edge(source, destination, weight) for each edge.

2

Set the number of vertices

Create an integer variable called verticesCount and set it to 5.

DSA C#

using System;
using System.Collections.Generic;

class Edge
{
    public int Source, Destination, Weight;
    public Edge(int source, int destination, int weight)
    {
        Source = source;
        Destination = destination;
        Weight = weight;
    }
}

class Program
{
    static void Main()
    {
        List edges = new List
        {
            new Edge(0, 1, 6),
            new Edge(0, 2, 7),
            new Edge(1, 2, 8),
            new Edge(1, 3, 5),
            new Edge(1, 4, -4),
            new Edge(2, 3, -3),
            new Edge(2, 4, 9),
            new Edge(3, 1, -2),
            new Edge(4, 0, 2),
            new Edge(4, 3, 7)
        };
        // Create verticesCount variable
        // Your code here
    }
}

Hint

Use int verticesCount = 5; to set the number of vertices.

3

Implement the Bellman Ford algorithm

Create an integer array called distances of size verticesCount. Initialize all values to int.MaxValue except distances[0] which should be 0. Then, run the Bellman Ford algorithm by relaxing all edges verticesCount - 1 times using a for loop with variable i and a nested foreach loop with variable edge over edges. Update distances[edge.Destination] if a shorter path is found from distances[edge.Source] plus edge.Weight.

DSA C#

using System;
using System.Collections.Generic;

class Edge
{
    public int Source, Destination, Weight;
    public Edge(int source, int destination, int weight)
    {
        Source = source;
        Destination = destination;
        Weight = weight;
    }
}

class Program
{
    static void Main()
    {
        List edges = new List
        {
            new Edge(0, 1, 6),
            new Edge(0, 2, 7),
            new Edge(1, 2, 8),
            new Edge(1, 3, 5),
            new Edge(1, 4, -4),
            new Edge(2, 3, -3),
            new Edge(2, 4, 9),
            new Edge(3, 1, -2),
            new Edge(4, 0, 2),
            new Edge(4, 3, 7)
        };
        int verticesCount = 5;
        // Initialize distances and run Bellman Ford
        // Your code here
    }
}

Hint

Initialize distances with int.MaxValue except for the start vertex 0. Use nested loops to relax edges.

4

Print the shortest distances

Use a for loop with variable i from 0 to verticesCount - 1 to print the shortest distance to each vertex in the format "Distance to vertex i is distances[i]". If the distance is int.MaxValue, print "Distance to vertex i is Infinity" instead.

DSA C#

using System;
using System.Collections.Generic;

class Edge
{
    public int Source, Destination, Weight;
    public Edge(int source, int destination, int weight)
    {
        Source = source;
        Destination = destination;
        Weight = weight;
    }
}

class Program
{
    static void Main()
    {
        List edges = new List
        {
            new Edge(0, 1, 6),
            new Edge(0, 2, 7),
            new Edge(1, 2, 8),
            new Edge(1, 3, 5),
            new Edge(1, 4, -4),
            new Edge(2, 3, -3),
            new Edge(2, 4, 9),
            new Edge(3, 1, -2),
            new Edge(4, 0, 2),
            new Edge(4, 3, 7)
        };
        int verticesCount = 5;

        int[] distances = new int[verticesCount];
        for (int i = 0; i < verticesCount; i++)
        {
            distances[i] = int.MaxValue;
        }
        distances[0] = 0;

        for (int i = 1; i <= verticesCount - 1; i++)
        {
            foreach (Edge edge in edges)
            {
                if (distances[edge.Source] != int.MaxValue && distances[edge.Source] + edge.Weight < distances[edge.Destination])
                {
                    distances[edge.Destination] = distances[edge.Source] + edge.Weight;
                }
            }
        }
        // Print shortest distances
        // Your code here
    }
}

Hint

Use a for loop to print each distance. Check if the distance is int.MaxValue to print "Infinity".

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