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.