Bellman Ford Algorithm Negative Weights in DSA C

Mental Model

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

Analogy: Imagine you want to find the cheapest route between cities, but some roads give discounts (negative costs). You check all roads repeatedly to update your best prices until no cheaper route is found.

Graph with nodes and edges:

  (A)
  / \
-1   4
 /     \
(B)---(C)
  \    /
   2  -3
    \ /
    (D)

Edges have weights, some negative (-1, -3).

Dry Run Walkthrough

Input: Graph with edges: A->B(-1), A->C(4), B->C(3), B->D(2), D->B(1), D->C(-3), start=A

Goal: Find shortest distances from A to all nodes, handling negative weights correctly

Step 1: Initialize distances: A=0, others=∞

Distances: A=0, B=∞, C=∞, D=∞

Why: Start with source distance zero and others unknown

Step 2: Relax edge A->B(-1): update B=0+(-1)=-1

Distances: A=0, B=-1, C=∞, D=∞

Why: Found cheaper path to B via A

Step 3: Relax edge A->C(4): update C=0+4=4

Distances: A=0, B=-1, C=4, D=∞

Why: Found initial path to C

Step 4: Relax edge B->C(3): update C=min(4, -1+3=2)=2

Distances: A=0, B=-1, C=2, D=∞

Why: Found cheaper path to C via B

Step 5: Relax edge B->D(2): update D=∞ to -1+2=1

Distances: A=0, B=-1, C=2, D=1

Why: Found path to D via B

Step 6: Relax edge D->C(-3): update C=min(2, 1+(-3)=-2)=-2

Distances: A=0, B=-1, C=-2, D=1

Why: Found cheaper path to C via D

Step 7: Relax edge D->B(1): update B=min(-1, 1+1=2)=-1 (no change)

Distances: A=0, B=-1, C=-2, D=1

Why: No improvement for B

Step 8: Repeat relaxation for all edges up to |V|-1 times to ensure shortest paths

Distances stabilize at A=0, B=-1, C=-2, D=1

Why: Multiple passes ensure all shortest paths found even with negative edges

Result:

Final distances: A=0, B=-1, C=-2, D=1

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>

#define V 4
#define E 6

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

void bellmanFord(Edge edges[], int n, int src) {
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < n; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int w = edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative weight cycles
    for (int j = 0; j < n; j++) {
        int u = edges[j].src;
        int v = edges[j].dest;
        int w = edges[j].weight;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("Graph contains negative weight cycle\n");
            return;
        }
    }

    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%c\t%d\n", 'A' + i, dist[i]);
    }
}

int main() {
    Edge edges[E] = {
        {0, 1, -1}, // A->B
        {0, 2, 4},  // A->C
        {1, 2, 3},  // B->C
        {1, 3, 2},  // B->D
        {3, 1, 1},  // D->B
        {3, 2, -3}  // D->C
    };

    bellmanFord(edges, E, 0); // Start from A (0)
    return 0;
}

dist[src] = 0;

Initialize source distance to zero

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

Repeat relaxation for all edges V-1 times

if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {

Relax edge if shorter path found

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

Update distance to destination node

if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {

Check for negative weight cycle after relaxation

printf("Graph contains negative weight cycle\n");

Report negative cycle if detected

Output

Vertex Distance from Source

A	0

B	-1

C	-2

D	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] != INT_MAX && dist[u] + w < dist[v]) { printf("Graph contains negative weight cycle\n"); return; }

Graph with no edges

Distances remain infinite except source zero

DSA C

dist[src] = 0;

Single vertex graph

Distance to source is zero, no edges to relax

DSA C

dist[src] = 0;

When to Use This Pattern

When you see shortest path problems with possible negative edge weights, reach for Bellman Ford because it handles negatives and detects cycles.

Common Mistakes

Mistake: Not repeating edge relaxation V-1 times
Fix: Use a loop to relax all edges V-1 times to ensure shortest paths

Mistake: Not checking for negative weight cycles
Fix: Add a final check after relaxation to detect cycles

Summary

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

Use when graph edges can have negative weights and cycle detection is needed.

Relax all edges repeatedly to update shortest distances until stable.

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