Bellman Ford Algorithm Negative Weights in DSA C++

Mental Model

Bellman Ford finds shortest paths even when edges have negative weights by relaxing edges multiple times.

Analogy: Imagine sending messages through a network of friends where some messages reduce your total cost. You keep updating your best known cost after hearing from each friend until no better cost is found.

Graph:
  (0)---5--->(1)
   |         /
  -3        /-4
   |       /
  (2)---->(3)

Edges have weights, some negative.

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0->1(5), 0->2(-3), 1->3(-4), 2->3(2). Start at node 0.

Goal: Find shortest distances from node 0 to all others, handling negative weights correctly.

Step 1: Initialize distances: dist[0]=0, others=∞

dist: [0, ∞, ∞, ∞]

Why: Start with source distance zero and unknown for others

Step 2: Relax edge 0->1(5): dist[1] = min(∞, 0+5) = 5

dist: [0, 5, ∞, ∞]

Why: Found a path to node 1 with cost 5

Step 3: Relax edge 0->2(-3): dist[2] = min(∞, 0+(-3)) = -3

dist: [0, 5, -3, ∞]

Why: Found a cheaper path to node 2 with negative cost

Step 4: Relax edge 1->3(-4): dist[3] = min(∞, 5+(-4)) = 1

dist: [0, 5, -3, 1]

Why: Found path to node 3 via node 1

Step 5: Relax edge 2->3(2): dist[3] = min(1, -3+2) = -1

dist: [0, 5, -3, -1]

Why: Found cheaper path to node 3 via node 2

Step 6: Repeat relaxation for all edges to confirm no further improvements

dist: [0, 5, -3, -1]

Why: No changes means shortest paths found

Result:

dist: [0, 5, -3, -1]

Annotated Code

DSA C++

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

struct Edge {
    int src, dest, weight;
};

void bellmanFord(int V, int E, vector<Edge>& edges, int src) {
    vector<int> dist(V, numeric_limits<int>::max());
    dist[src] = 0;

    // Relax edges V-1 times
    for (int i = 1; i <= V - 1; ++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] != numeric_limits<int>::max() && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative weight cycles
    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] != numeric_limits<int>::max() && dist[u] + w < dist[v]) {
            cout << "Graph contains negative weight cycle" << endl;
            return;
        }
    }

    // Print distances
    for (int i = 0; i < V; ++i) {
        cout << "Distance from node " << src << " to node " << i << " is ";
        if (dist[i] == numeric_limits<int>::max())
            cout << "Infinity" << endl;
        else
            cout << dist[i] << endl;
    }
}

int main() {
    int V = 4; // number of vertices
    int E = 4; // number of edges
    vector<Edge> edges(E);

    edges[0] = {0, 1, 5};
    edges[1] = {0, 2, -3};
    edges[2] = {1, 3, -4};
    edges[3] = {2, 3, 2};

    bellmanFord(V, E, edges, 0);
    return 0;
}

dist[src] = 0;

Initialize source distance to zero

for (int i = 1; i <= V - 1; ++i) {

Repeat relaxation V-1 times to ensure shortest paths

if (dist[u] != numeric_limits<int>::max() && dist[u] + w < dist[v]) {

Relax edge if current path improves distance

dist[v] = dist[u] + w;

Update distance to shorter path

if (dist[u] != numeric_limits<int>::max() && dist[u] + w < dist[v]) {

Check for negative weight cycle by detecting further relaxation

cout << "Distance from node " << src << " to node " << i << " is ";

Print final shortest distances

Output

Distance from node 0 to node 0 is 0

Distance from node 0 to node 1 is 5

Distance from node 0 to node 2 is -3

Distance from node 0 to node 3 is -1

Complexity Analysis

Time: O(V * E) because we relax all edges V-1 times

Space: O(V) for storing distances to each vertex

vs Alternative: Dijkstra is faster O(E + V log V) but cannot handle negative weights; Bellman Ford handles negatives but is slower

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and reports it

DSA C++

if (dist[u] != numeric_limits<int>::max() && dist[u] + w < dist[v]) { cout << "Graph contains negative weight cycle" << endl; return; }

Graph with unreachable nodes

Distances remain Infinity for unreachable nodes

DSA C++

if (dist[i] == numeric_limits<int>::max()) cout << "Infinity" << endl;

Graph with zero edges

Distances remain Infinity except source node

DSA C++

dist[src] = 0;

When to Use This Pattern

When you need shortest paths but edges can have negative weights, use Bellman Ford because it handles negatives and detects cycles.

Common Mistakes

Mistake: Not relaxing edges V-1 times, leading to incorrect distances
Fix: Always repeat relaxation exactly V-1 times to ensure all shortest paths are found

Mistake: Not checking for negative weight cycles after relaxation
Fix: Add a final check to detect if any edge can still be relaxed, indicating a negative cycle

Summary

Finds shortest paths from a source even with negative edge weights.

Use when graph edges can have negative weights and you need to detect negative cycles.

Relax all edges multiple times until no shorter paths are found or a negative cycle is detected.

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