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 after running Bellman-Ford on the given graph with 5 vertices and edges including negative weights?

DSA C

int V = 5;
int E = 8;
int edges[8][3] = {
  {0, 1, -1},
  {0, 2, 4},
  {1, 2, 3},
  {1, 3, 2},
  {1, 4, 2},
  {3, 2, 5},
  {3, 1, 1},
  {4, 3, -3}
};

int dist[5] = {0, 10000, 10000, 10000, 10000};

// Bellman-Ford relaxation loop
for (int i = 1; i <= V - 1; i++) {
  for (int j = 0; j < E; j++) {
    int u = edges[j][0];
    int v = edges[j][1];
    int w = edges[j][2];
    if (dist[u] != 10000 && dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

// Print distances
for (int i = 0; i < V; i++) {
  printf("%d ", dist[i]);
}

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

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

C [0, 0, 4, 1, 2]

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

💡 Hint

Trace the relaxation steps carefully for each edge over 4 iterations.

The Bellman-Ford algorithm relaxes edges V-1 times. Negative edges reduce distances correctly. The final distances are [0, -1, 2, -2, 1].

🧠 Conceptual

intermediate

Detecting negative weight cycles with Bellman-Ford

Which statement correctly describes how Bellman-Ford detects negative weight cycles?

A If the graph has any negative edge, Bellman-Ford always detects a negative cycle.

B If after V-1 iterations, any edge can still be relaxed, a negative weight cycle exists.

C Bellman-Ford detects negative cycles by checking if distances become negative at any point.

D Bellman-Ford cannot detect negative weight cycles.

💡 Hint

Think about what happens if distances keep decreasing after all relaxations.

Bellman-Ford runs V-1 relaxations. If any edge can still reduce distance after that, it means a cycle with negative total weight exists.

🔧 Debug

advanced

Identify the bug in this Bellman-Ford implementation snippet

What is the bug in this code snippet for Bellman-Ford algorithm?

DSA C

for (int i = 0; i < V; i++) {
  for (int j = 0; j < E; j++) {
    int u = edges[j][0];
    int v = edges[j][1];
    int w = edges[j][2];
    if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

A The outer loop should run V-1 times, not V times.

B The inner loop should run V times, not E times.

C The distance array should be initialized with zeros, not INT_MAX.

D The condition dist[u] != INT_MAX is incorrect and should be removed.

💡 Hint

Recall how many times Bellman-Ford relaxes edges.

Bellman-Ford requires exactly V-1 iterations of edge relaxation. Running V times is unnecessary and may cause incorrect behavior.

❓ Predict Output

advanced

Output after detecting negative cycle in Bellman-Ford

What will the program print after running Bellman-Ford on a graph with a negative weight cycle?

DSA C

int V = 3;
int E = 3;
int edges[3][3] = {
  {0, 1, 1},
  {1, 2, -1},
  {2, 0, -1}
};

int dist[3] = {0, 10000, 10000};

for (int i = 1; i <= V - 1; i++) {
  for (int j = 0; j < E; j++) {
    int u = edges[j][0];
    int v = edges[j][1];
    int w = edges[j][2];
    if (dist[u] != 10000 && dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

// Check for negative cycle
int negative_cycle = 0;
for (int j = 0; j < E; j++) {
  int u = edges[j][0];
  int v = edges[j][1];
  int w = edges[j][2];
  if (dist[u] != 10000 && dist[u] + w < dist[v]) {
    negative_cycle = 1;
    break;
  }
}

if (negative_cycle) {
  printf("Negative cycle detected\n");
} else {
  for (int i = 0; i < V; i++) {
    printf("%d ", dist[i]);
  }
}

A Negative cycle detected

B 0 1 0

C 0 10000 10000

D 0 -1 -2

💡 Hint

Check if any edge can still relax after V-1 iterations.

The cycle 0->1->2->0 has total negative weight, so the check detects a negative cycle and prints the message.

🚀 Application

expert

Choosing Bellman-Ford over Dijkstra for shortest paths

In which scenario is Bellman-Ford algorithm preferred over Dijkstra's algorithm?

A When the graph has no edges.

B When the graph is very large and all edges have positive weights.

C When the graph contains negative weight edges but no negative weight cycles.

D When the graph is dense and edges have only positive weights.

💡 Hint

Consider which algorithm handles negative weights correctly.

Dijkstra's algorithm fails with negative weights. Bellman-Ford works correctly even with negative edges if no negative cycles exist.

Practice

1. What is the main advantage of the Bellman-Ford algorithm compared to Dijkstra's algorithm?

easy

A. It only works on directed acyclic graphs.

B. It runs faster on all graphs.

C. It uses less memory.

D. It can handle graphs with negative weight edges.

Solution

1. Step 1: Understand the limitation of Dijkstra's algorithm

   Dijkstra's algorithm cannot correctly handle graphs with negative weight edges because it assumes that once a node's shortest path is found, it cannot be improved.

2. Step 2: Recognize Bellman-Ford's capability

   Bellman-Ford algorithm can handle negative weight edges and detect negative weight cycles, making it more versatile.

3. Final Answer:

   It can handle graphs with negative weight edges. -> Option D

4. Quick Check:

   Negative weights handled = A [OK]

Hint: Bellman-Ford works with negative edges; Dijkstra does not [OK]

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Assuming it uses less memory
• Believing it only works on acyclic graphs

2. Which of the following is the correct way to initialize the distance array in Bellman-Ford algorithm in C?

easy

A. int dist[V]; for(int i=0; i

B. int dist[V]; for(int i=0; i

C. int dist[V]; for(int i=0; i

D. int dist[V]; for(int i=0; i

Solution

1. Step 1: Understand distance initialization

   Distances to all vertices except the source should be set to a very large number (infinity), here represented by INT_MAX, to indicate they are initially unreachable.

2. Step 2: Set source distance to zero

   The distance to the source vertex itself must be zero because the shortest path from source to source is zero.

3. Final Answer:

   int dist[V]; for(int i=0; i -> Option B

4. Quick Check:

   Initialize all to max, source to 0 = C [OK]

Hint: Set all distances to INT_MAX except source = 0 [OK]

Common Mistakes:

• Initializing all distances to zero
• Using -1 for unreachable distances
• Setting all distances to source index

3. What will be the output distances array after running Bellman-Ford on this graph with edges:
edges = [(0,1,4), (0,2,5), (1,2,-3), (2,3,4)] starting from source 0?

medium

A. [0, 4, 1, 5]

B. [0, 4, 1, 9]

C. [0, 4, 5, 9]

D. [0, 4, -3, 4]

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF]

2. Step 2: Relax edges repeatedly

   First iteration:
   dist[1] = min(INF, 0+4) = 4
   dist[2] = min(INF, 0+5) = 5
   dist[2] = min(5, 4 + (-3)) = 1
   dist[3] = min(INF, 1 + 4) = 5
   Second iteration:
   dist[1] stays 4
   dist[2] stays 1
   dist[3] stays 5
   No further updates.

3. Final distances:

   [0, 4, 1, 5]

4. Final Answer:

   [0, 4, 1, 5] -> Option A

5. Quick Check:

   Relax edges to update distances = A [OK]

Hint: Relax edges V-1 times to update shortest paths [OK]

Common Mistakes:

• Not relaxing edges enough times
• Ignoring negative edge effect
• Wrong initial distances

4. Identify the error in this Bellman-Ford code snippet in C:

for (int i = 0; i < V; i++) {
  for (int j = 0; j < E; j++) {
    int u = edges[j].src;
    int v = edges[j].dest;
    int w = edges[j].weight;
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. The outer loop should run V-1 times, not V times.

B. The inner loop should run V times, not E times.

C. The distance array is not initialized.

D. The weight comparison should be dist[v] + w < dist[u].

Solution

1. Step 1: Check loop iteration count

   Bellman-Ford requires relaxing edges exactly V-1 times to find shortest paths correctly.

2. Step 2: Identify the incorrect loop count

   The outer loop runs V times here, which is one extra iteration and unnecessary.

3. Final Answer:

   The outer loop should run V-1 times, not V times. -> Option A

4. Quick Check:

   Outer loop runs V-1 times = D [OK]

Hint: Relax edges exactly V-1 times for correct shortest paths [OK]

Common Mistakes:

• Running outer loop V times instead of V-1
• Confusing inner loop count with vertex count
• Incorrect weight comparison direction

5. Given a graph with edges
[(0,1,1), (1,2,-1), (2,3,-1), (3,1,-1)], what will Bellman-Ford detect when run from source 0?

hard

A. It will run infinitely without stopping.

B. It will find shortest paths without any issues.

C. It will detect a negative weight cycle.

D. It will give incorrect distances but no error.

Solution

1. Step 1: Analyze the cycle in the graph

   The edges (1->2), (2->3), and (3->1) form a cycle with total weight -1 + -1 + -1 = -3, which is negative.

2. Step 2: Understand Bellman-Ford's negative cycle detection

   Bellman-Ford detects negative weight cycles by checking for further relaxation after V-1 iterations. Here, it will detect the negative cycle.

3. Final Answer:

   It will detect a negative weight cycle. -> Option C

4. Quick Check:

   Negative cycle detected = A [OK]

Hint: Negative cycle if distances keep decreasing after V-1 relaxations [OK]

Common Mistakes:

• Assuming algorithm runs infinitely
• Believing it finds shortest paths despite negative cycle
• Ignoring cycle detection step