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.