Bellman Ford Algorithm Negative Weights in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bellman-Ford on a graph with negative edges

What is the shortest distance array output after running Bellman-Ford on the given graph from source vertex 0?

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, E;
    public List<Edge> edges;
    public Graph(int v, int e) {
        V = v; E = e;
        edges = new List<Edge>();
    }

    public int[] BellmanFord(int src) {
        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) {
                int u = edge.Src, v = edge.Dest, w = edge.Weight;
                if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        return dist;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(5, 8);
        g.edges.Add(new Edge(0, 1, -1));
        g.edges.Add(new Edge(0, 2, 4));
        g.edges.Add(new Edge(1, 2, 3));
        g.edges.Add(new Edge(1, 3, 2));
        g.edges.Add(new Edge(1, 4, 2));
        g.edges.Add(new Edge(3, 2, 5));
        g.edges.Add(new Edge(3, 1, 1));
        g.edges.Add(new Edge(4, 3, -3));

        int[] dist = g.BellmanFord(0);
        Console.WriteLine(string.Join(",", dist));
    }
}

A [0, -1, 2, -2, 1]

B [0, -1, 3, 0, 2]

C [0, 1, 4, 1, 3]

D [0, -1, 2, 1, 1]

💡 Hint

Trace the relaxation steps carefully for each edge over V-1 iterations.

The Bellman-Ford algorithm relaxes edges repeatedly. After 4 iterations (V-1), the shortest distances from source 0 to all vertices are [0, -1, 2, -2, 1].

🧠 Conceptual

intermediate

Detecting negative weight cycles with Bellman-Ford

After running Bellman-Ford for V-1 iterations, what is the next step to detect if a negative weight cycle exists in the graph?

A Check if all distances are positive; if yes, no negative cycle exists.

B Check if any edge can still be relaxed; if yes, a negative weight cycle exists.

C Run Dijkstra's algorithm to confirm negative cycles.

D Check if the source vertex distance changed in the last iteration.

💡 Hint

Think about what relaxation means after all iterations.

If after V-1 iterations, any edge can still reduce the distance, it means a cycle with negative total weight exists.

🔧 Debug

advanced

Identify the bug in this Bellman-Ford implementation

What is the bug in the following Bellman-Ford code snippet that causes incorrect shortest path calculation?

DSA C#

for (int i = 1; i <= V; i++) {
    foreach (var edge in edges) {
        int u = edge.Src, v = edge.Dest, w = edge.Weight;
        if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
        }
    }
}

A The distance array is not initialized to int.MaxValue for all vertices.

B Edges are not sorted before relaxation, causing wrong results.

C The condition dist[u] != int.MaxValue is missing, causing null reference errors.

D The loop runs V times instead of V-1 times, causing unnecessary extra relaxation.

💡 Hint

Recall how many times edges should be relaxed in Bellman-Ford.

The Bellman-Ford algorithm requires relaxing edges exactly V-1 times. Running V times is unnecessary and may cause incorrect behavior.

❓ Predict Output

advanced

Output when graph contains a negative weight cycle

What will the Bellman-Ford algorithm output or detect when run on a graph with a reachable negative weight cycle?

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, E;
    public List<Edge> edges;
    public Graph(int v, int e) {
        V = v; E = e;
        edges = new List<Edge>();
    }

    public bool BellmanFord(int src, out int[] dist) {
        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) {
                int u = edge.Src, v = edge.Dest, w = edge.Weight;
                if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        foreach (var edge in edges) {
            int u = edge.Src, v = edge.Dest, w = edge.Weight;
            if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
                return false; // Negative cycle detected
            }
        }
        return true;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(3, 3);
        g.edges.Add(new Edge(0, 1, 1));
        g.edges.Add(new Edge(1, 2, -1));
        g.edges.Add(new Edge(2, 0, -1));

        bool noNegativeCycle = g.BellmanFord(0, out int[] dist);
        Console.WriteLine(noNegativeCycle ? string.Join(",", dist) : "Negative cycle detected");
    }
}

A 0,1,-1

B 0,1,0

C Negative cycle detected

D 0,2147483647,2147483647

💡 Hint

Check the final cycle detection step after all relaxations.

The algorithm detects the negative cycle and returns false, printing "Negative cycle detected".

🧠 Conceptual

expert

Why Bellman-Ford is preferred over Dijkstra for graphs with negative weights

Which reason best explains why Bellman-Ford algorithm is used instead of Dijkstra's algorithm when graphs have negative edge weights?

A Bellman-Ford correctly handles negative weights and detects negative cycles, while Dijkstra fails with negative edges.

B Bellman-Ford is faster than Dijkstra on all graphs.

C Dijkstra cannot find shortest paths in graphs with cycles.

D Bellman-Ford uses less memory than Dijkstra.

💡 Hint

Think about how negative weights affect shortest path algorithms.

Dijkstra's algorithm assumes all edge weights are non-negative. It fails or gives incorrect results if negative edges exist. Bellman-Ford handles negative weights and detects negative 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