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 node 0?

DSA C++

/* Graph edges: (u, v, w) */
// (0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 4), (3, 1, 6)
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

struct Edge {
    int u, v, w;
};

int main() {
    int V = 4;
    int E = 5;
    vector<Edge> edges = {{0,1,4},{0,2,5},{1,2,-3},{2,3,4},{3,1,6}};
    vector<int> dist(V, numeric_limits<int>::max());
    dist[0] = 0;

    for (int i = 1; i <= V - 1; i++) {
        for (auto &e : edges) {
            if (dist[e.u] != numeric_limits<int>::max() && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }

    cout << "Distances: ";
    for (int d : dist) cout << d << " ";
    cout << endl;
    return 0;
}

A [0, 4, 5, 9]

B [0, 4, 1, 5]

C [0, 10, 7, 11]

D [0, -3, 1, 5]

💡 Hint

Remember Bellman-Ford relaxes edges V-1 times and updates distances if a shorter path is found.

The algorithm starts with dist[0] = 0 and others infinity. After first iteration, dist[1] = 4, dist[2] = 5. Then relaxing edge (1,2,-3) updates dist[2] to 1 (4 + -3). Next, dist[3] becomes 5 (1 + 4). No further improvements after V-1 iterations. So final distances are [0, 4, 1, 5].

🧠 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 Count the number of edges relaxed in the last iteration

B Check if any distance is still infinity

C Run Dijkstra's algorithm to confirm negative cycles

D Run one more iteration over all edges and check if any distance can still be updated

💡 Hint

Negative cycles allow distances to keep decreasing after V-1 relaxations.

If after V-1 iterations, any edge can still relax a distance, it means a negative cycle exists because distances should have stabilized otherwise.

🔧 Debug

advanced

Identify the bug in this Bellman-Ford implementation snippet

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

DSA C++

for (int i = 0; i < V; i++) {
    for (auto &e : edges) {
        if (dist[e.u] + e.w < dist[e.v]) {
            dist[e.v] = dist[e.u] + e.w;
        }
    }
}

A dist array is not initialized with infinity

B The condition should check dist[e.v] + e.w < dist[e.u]

C The outer loop should run V-1 times, not V times

D Edges should be relaxed in reverse order

💡 Hint

Bellman-Ford requires exactly V-1 iterations to guarantee shortest paths.

The code runs the relaxation loop V times instead of V-1 times. Bellman-Ford requires exactly V-1 iterations to find the shortest paths (in terms of simple paths). An extra iteration is typically used only for detecting negative cycles.

❓ Predict Output

advanced

Output after detecting negative cycle

What will the program output after running Bellman-Ford on this graph with edges: (0,1,1), (1,2,-1), (2,0,-1) from source 0?

DSA C++

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

struct Edge {
    int u, v, w;
};

int main() {
    int V = 3;
    int E = 3;
    vector<Edge> edges = {{0,1,1},{1,2,-1},{2,0,-1}};
    vector<int> dist(V, numeric_limits<int>::max());
    dist[0] = 0;

    for (int i = 1; i <= V - 1; i++) {
        for (auto &e : edges) {
            if (dist[e.u] != numeric_limits<int>::max() && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }

    bool negative_cycle = false;
    for (auto &e : edges) {
        if (dist[e.u] != numeric_limits<int>::max() && dist[e.u] + e.w < dist[e.v]) {
            negative_cycle = true;
            break;
        }
    }

    if (negative_cycle) cout << "Negative cycle detected" << endl;
    else {
        cout << "Distances: ";
        for (int d : dist) cout << d << " ";
        cout << endl;
    }
    return 0;
}

A Negative cycle detected

B Distances: 0 1 -1

C Distances: 0 1 0

D Distances: 0 0 0

💡 Hint

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

The cycle 0->1->2->0 has total weight 1 + (-1) + (-1) = -1, which is negative. After V-1 iterations, distances can still be improved, so the program detects a negative cycle and prints the message.

🧠 Conceptual

expert

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

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

A Bellman-Ford can handle negative weights and detect negative cycles, while Dijkstra cannot handle negative weights correctly

B Dijkstra's algorithm only works on directed acyclic graphs

C Bellman-Ford uses less memory than Dijkstra's algorithm

D Dijkstra's algorithm is slower than Bellman-Ford for all graphs

💡 Hint

Think about how negative weights affect shortest path calculations.

Dijkstra's algorithm assumes all edge weights are non-negative to guarantee correctness. It fails or gives wrong results if negative weights exist. Bellman-Ford handles negative weights and can detect negative cycles.

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: Identify Bellman Ford's capability

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

3. Final Answer:

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

4. Quick Check:

   Negative weights handled = D [OK]

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

Common Mistakes:

• Thinking Bellman Ford is always faster than Dijkstra
• Believing Bellman Ford cannot detect negative cycles
• Assuming Bellman Ford 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. vector<int> dist(V, 0); dist[src] = INT_MAX;

B. vector<int> dist(V, INT_MAX); dist[src] = 0;

C. vector<int> dist(V, -1); dist[src] = 0;

D. vector<int> dist(V, INT_MIN); dist[src] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances to all vertices except the source should be set to a very large number (infinity equivalent), here INT_MAX, to represent unknown distance.

2. Step 2: Set source distance to zero

   The source vertex distance is zero because the distance from source to itself is zero.

3. Final Answer:

   vector<int> dist(V, INT_MAX); dist[src] = 0; -> Option B

4. Quick Check:

   Initialize with INT_MAX and source zero = B [OK]

Hint: Initialize all distances to INT_MAX except source zero [OK]

Common Mistakes:

• Setting all distances to zero
• Using INT_MIN which is incorrect for distances
• Not setting source distance to zero

3. Consider the following graph edges and weights:

Edges: (0->1, 4), (0->2, 5), (1->2, -3), (2->3, 4), (3->1, 6)

What is the shortest distance from vertex 0 to vertex 3 after running Bellman Ford?

medium

A. 5

B. 9

C. 6

D. 7

Solution

1. Step 1: Initialize distances

   dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞.

2. Step 2: Relax edges repeatedly

   After first iteration: dist[1]=4, dist[2]=5, dist[3]=∞.
   Relax (1->2): dist[2]=4 + (-3) = 1.
   Relax (2->3): dist[3]=1 + 4 = 5.
   Relax (3->1): dist[1]=min(4, 5 + 6=11) = 4.
   Second iteration: No further improvements.
   Final dist[3] = 5.

3. Step 3: Check for negative cycles

   No negative cycle detected.

4. Final Answer:

   5 -> Option A

5. Quick Check:

   Shortest path dist to 3 = 5 [OK]

Hint: Relax edges V-1 times, track minimum distances [OK]

Common Mistakes:

• Not updating distances after negative edge relaxation
• Confusing edge directions
• Stopping relaxation too early

4. The following C++ code snippet attempts to implement Bellman Ford but has a bug:

for (int i = 0; i < V; i++) {
  for (auto edge : edges) {
    if (dist[edge.u] + edge.w < dist[edge.v]) {
      dist[edge.v] = dist[edge.u] + edge.w;
    }
  }
}

What is the bug?

medium

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

B. The condition should use <= instead of <.

C. The distance array is not initialized.

D. Edges should be relaxed in reverse order.

Solution

1. Step 1: Understand Bellman Ford iteration count

   Bellman Ford requires relaxing edges exactly V-1 times to find shortest paths without negative cycles.

2. Step 2: Identify the loop error

   The code runs the outer loop V times, which is one extra iteration and may cause incorrect detection of negative cycles or unnecessary work.

3. Final Answer:

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

4. Quick Check:

   Outer loop count = V-1 [OK]

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

Common Mistakes:

• Running outer loop V times instead of V-1
• Changing comparison operator incorrectly
• Ignoring distance initialization

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 vertex 0?

hard

A. Graph is disconnected.

B. Shortest distances without any issues.

C. A negative weight cycle reachable from source.

D. Algorithm will run infinitely.

Solution

1. Step 1: Identify 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 reachable from the source by checking if any edge can still be relaxed after V-1 iterations.

3. Step 3: Conclusion

   Since the negative cycle is reachable from vertex 0, Bellman Ford will detect it and report its presence.

4. Final Answer:

   A negative weight cycle reachable from source. -> Option C

5. Quick Check:

   Negative cycle detected = A [OK]

Hint: Negative cycle if edges relax after V-1 iterations [OK]

Common Mistakes:

• Ignoring negative cycles reachable from source
• Assuming algorithm runs infinitely
• Thinking graph is disconnected