Bellman Ford Algorithm Negative Weights in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with infinity except the source vertex.

DSA C#

int[] dist = new int[V];
for (int i = 0; i < V; i++) {
    dist[i] = [1];
}
dist[src] = 0;

Drag options to blanks, or click blank then click option'

AV

Bint.MaxValue

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting distance to 0 for all vertices instead of only source.

Using -1 as initial distance which is incorrect.

We use int.MaxValue to represent infinity for initial distances except the source which is 0.

2fill in blank

medium

Complete the code to relax edges inside the main loop of Bellman-Ford.

DSA C#

for (int i = 1; i <= V - 1; i++) {
    foreach (var edge in edges) {
        int u = edge.src;
        int v = edge.dest;
        int weight = edge.weight;
        if (dist[u] != [1] && dist[u] + weight < dist[v]) {
            dist[v] = dist[u] + weight;
        }
    }
}

Drag options to blanks, or click blank then click option'

Aint.MaxValue

B0

C-1

DV

Attempts:

3 left

💡 Hint

Common Mistakes

Not checking if dist[u] is infinity before adding weight.

Using 0 or -1 instead of int.MaxValue in the condition.

We check if dist[u] is not infinity (int.MaxValue) before relaxing to avoid overflow.

3fill in blank

hard

Fix the error in the negative cycle detection condition.

DSA C#

foreach (var edge in edges) {
    int u = edge.src;
    int v = edge.dest;
    int weight = edge.weight;
    if (dist[u] != int.MaxValue && dist[u] + weight [1] dist[v]) {
        Console.WriteLine("Graph contains negative weight cycle");
    }
}

Drag options to blanks, or click blank then click option'

A<

B>=

C==

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' or '>=' which is incorrect for negative cycle detection.

Using '==' which does not detect negative cycles.

If we can still relax an edge (dist[u] + weight < dist[v]) after V-1 iterations, a negative cycle exists.

4fill in blank

hard

Fill both blanks to complete the edge relaxation inside the Bellman-Ford main loop.

DSA C#

for (int i = 1; i <= V - 1; i++) {
    foreach (var edge in edges) {
        int u = edge.src;
        int v = edge.dest;
        int weight = edge.weight;
        if (dist[u] != [1] && dist[u] + weight [2] dist[v]) {
            dist[v] = dist[u] + weight;
        }
    }
}

Drag options to blanks, or click blank then click option'

Aint.MaxValue

B<

C>

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operator in relaxation condition.

Not checking for infinity before relaxation.

We check dist[u] != int.MaxValue and relax if dist[u] + weight < dist[v].

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that stores shortest distances after Bellman-Ford.

DSA C#

var shortestPaths = new Dictionary<int, int>();
for (int i = 0; i < V; i++) {
    if (dist[i] != [1]) {
        shortestPaths[[2]] = dist[[3]];
    }
}

Drag options to blanks, or click blank then click option'

Aint.MaxValue

Bi

Ci + 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong key or value indices in dictionary.

Not checking for int.MaxValue before adding.

We skip vertices with distance int.MaxValue and store distances keyed by vertex index i.

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