With Code, Example, Diagrams & Analysis

Bellman-Ford Algorithm – Complete Comparison with Dijkstra

With Code, Example, Diagrams & Analysis

1. Overview: Bellman-Ford vs Dijkstra

Feature	Dijkstra	Bellman-Ford
Edge Weights	Non-negative only	Allows negative weights
Negative Cycles	Cannot detect	Detects negative cycles
Time Complexity	O((V+E) log V)	O(V × E)
Space Complexity	O(V)	O(V)
Greedy?	Yes	No (Dynamic Programming)
Best Use	Dense graphs, no negatives	Sparse graphs, negative edges

2. Bellman-Ford Algorithm

Finds shortest paths from a source in a graph with negative edge weights and detects negative cycles.

Key Idea

Relax all edges V-1 times → ensures shortest path is found (longest path in DAG is V-1 edges).

3. Algorithm Steps

1. Initialize:
   dist[source] = 0
   dist[others] = ∞

2. Relax all edges V-1 times:
   for i = 1 to V-1:
       for each edge (u,v,w):
           if dist[u] + w < dist[v]:
               dist[v] = dist[u] + w
               parent[v] = u

3. Check for negative cycle:
   for each edge (u,v,w):
       if dist[u] + w < dist[v]:
           → Negative cycle exists!

4. Example Graph (With Negative Edge)

    A
   / \  
  6   -2
 /     \
B-------C
  \    / \
   7  4   5
    \ |   |
     D----E
       -3

Edges List

u	v	w
A	B	6
A	C	-2
B	C	7
B	D	7
C	D	4
C	E	5
D	E	-3

5. Bellman-Ford Execution (Source = A)

Iteration	dist[B]	dist[C]	dist[D]	dist[E]
Init	∞	∞	∞	∞
1	6	-2	2	7
2	6	-2	2	-1
3	6	-2	2	-1

Converged after 2 iterations (V-1 = 4, but early convergence)

Final Distances

Node	Distance	Path
A	0	A
B	6	A → B
C	-2	A → C
D	2	A → C → D
E	-1	A → C → D → E

6. What if Negative Cycle?

Add edge: E → B with weight -10

Now: E → B (-10) → C (7) → D (4) → E (-3) = -12 < 0 → Negative Cycle!

Bellman-Ford detects it in V-th iteration!

7. Full C Code: Bellman-Ford

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

#define V 5
#define INF INT_MAX

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

typedef struct {
    Edge edges[100];
    int E;  // Number of edges
} Graph;

Graph* createGraph() {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->E = 0;
    return g;
}

void addEdge(Graph* g, int u, int v, int w) {
    g->edges[g->E].u = u;
    g->edges[g->E].v = v;
    g->edges[g->E++].w = w;
}

void bellmanFord(Graph* g, int src) {
    int dist[V], parent[V];
    for(int i = 0; i < V; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[src] = 0;

    // Relax V-1 times
    for(int i = 1; i <= V-1; i++) {
        int updated = 0;
        for(int j = 0; j < g->E; j++) {
            int u = g->edges[j].u;
            int v = g->edges[j].v;
            int w = g->edges[j].w;

            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                updated = 1;
            }
        }
        if (!updated) break;  // Early termination
    }

    // Check negative cycle
    for(int j = 0; j < g->E; j++) {
        int u = g->edges[j].u;
        int v = g->edges[j].v;
        int w = g->edges[j].w;

        if (dist[u] != INF && dist[u] + w < dist[v]) {
            printf("Negative cycle detected!\n");
            return;
        }
    }

    // Print result
    printf("Vertex\tDistance\tPath\n");
    for(int i = 0; i < V; i++) {
        printf("%c \t", 'A' + i);
        if(dist[i] == INF) printf("INF\t-\n");
        else {
            printf("%d\t", dist[i]);
            // Print path (recursive)
            int temp = i;
            while(temp != -1) {
                printf("%c ", 'A' + temp);
                temp = parent[temp];
                if(temp != -1) printf("← ");
            }
            printf("\n");
        }
    }
}

// Main
int main() {
    Graph* g = createGraph();

    addEdge(g, 0, 1, 6);   // A→B
    addEdge(g, 0, 2, -2);  // A→C
    addEdge(g, 1, 2, 7);   // B→C
    addEdge(g, 1, 3, 7);   // B→D
    addEdge(g, 2, 3, 4);   // C→D
    addEdge(g, 2, 4, 5);   // C→E
    addEdge(g, 3, 4, -3);  // D→E

    printf("Bellman-Ford (Source = A)\n");
    bellmanFord(g, 0);

    return 0;
}

8. Output

Bellman-Ford (Source = A)
Vertex  Distance       Path
A       0               A 
B       6               B ← A 
C       -2              C ← A 
D       2               D ← C ← A 
E       -1              E ← D ← C ← A

9. Comparison Table (Dijkstra vs Bellman-Ford)

Criteria	Dijkstra	Bellman-Ford
Negative Weights	Fails	Works
Negative Cycle Detection	No	Yes
Time Complexity	O((V+E) log V)	O(V × E)
Space	O(V)	O(V)
Implementation	Priority Queue (Heap)	Edge List
Best for Sparse Graph	Yes	No
Best for Dense Graph	Yes	No
Early Termination	Yes	Yes (with flag)
Used in	GPS, OSPF	RIP, Distance Vector

10. When to Use Which?

Scenario	Choose
All weights ≥ 0	Dijkstra (Faster)
Negative weights, no cycle	Bellman-Ford
Need to detect negative cycle	Bellman-Ford
Real-time routing (OSPF)	Dijkstra
Distance vector routing (RIP)	Bellman-Ford

11. Visual: Relaxation Process

Iteration 1:
A→B: 0+6 < ∞ → B=6
A→C: 0-2 < ∞ → C=-2
C→D: -2+4 → D=2
C→E: -2+5 → E=7

Iteration 2:
D→E: 2 + (-3) = -1 < 7 → E=-1

No change in Iteration 3 → Done

12. Negative Cycle Example

addEdge(g, 4, 1, -10);  // E→B (-10)

V-th Iteration:

E→B: -1 + (-10) = -11 < 6 → Update B!
→ Infinite loop possible → Negative cycle!

13. SPFA (Shortest Path Faster Algorithm)

Queue-based Bellman-Ford – Faster in practice

Use queue + inQueue[] array
Only relax nodes that were updated
Average: O(E), Worst: O(V×E)

14. Summary Table

Feature	Dijkstra	Bellman-Ford
Speed	Fast	Slow
Negative Edges	No	Yes
Cycle Detection	No	Yes
Code Complexity	Medium	Simple
Real-world Use	GPS	RIP

15. Practice Problems

Find shortest path with negative weights
Detect negative cycle in currency exchange
Compare runtime: Dijkstra vs Bellman-Ford on 1000 nodes
Implement SPFA
Modify Bellman-Ford to return path

Key Takeaways

Dijkstra → Fast, non-negative only
Bellman-Ford → Robust, handles negatives, detects cycles

Use Bellman-Ford when in doubt about edge weights!

End of Comparison