DSA Bellman Ford Algorithm

DSA Bellman Ford Algorithm

(Concept • Steps • Example • Code • Negative Cycles • Complexity)

The DSA Bellman Ford Algorithm finds the shortest paths from a single source to all other vertices in a weighted graph, even when negative edge weights exist.
It’s a must-know algorithm for interviews and theory questions.

1️⃣ What Problem Does Bellman–Ford Solve?

Given:

A weighted graph (directed or undirected)
Negative edge weights allowed
A source vertex

Find:

Shortest distance from the source to every other vertex
Detect negative weight cycles

2️⃣ When to Use Bellman–Ford

Scenario	Use Bellman–Ford?
Unweighted graph	❌ (Use BFS)
Weighted, all weights ≥ 0	❌ (Use Dijkstra)
Weighted, negative edges	✅
Need to detect negative cycle	✅

3️⃣ Core Idea (Relaxation)

Initialize distances with ∞, source = 0
Relax all edges repeatedly
Do this V − 1 times (V = number of vertices)

Why V − 1?
The longest simple path in a graph has at most V − 1 edges.

4️⃣ Key Term: Relaxation

For an edge u → v with weight w:

This tries to improve the shortest distance.

5️⃣ Step-by-Step Example

Graph

Source = 0

Initial

After V−1 Relaxations

Extra Pass (Cycle Check)

If any distance still improves → negative cycle exists

6️⃣ Algorithm Steps

Initialize dist[] with ∞
Set dist[source] = 0
Repeat V − 1 times:
- Relax all edges
Repeat once more:
- If any distance updates → negative cycle

7️⃣ C++ Implementation (Bellman–Ford)

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

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

void bellmanFord(int V, int src, vector<Edge>& edges) {
    vector<int> dist(V, 1e9);
    dist[src] = 0;

    // Step 1: Relax edges V-1 times
    for(int i = 1; i <= V - 1; i++) {
        for(auto e : edges) {
            if(dist[e.u] != 1e9 && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }

    // Step 2: Check for negative weight cycle
    for(auto e : edges) {
        if(dist[e.u] != 1e9 && dist[e.u] + e.w < dist[e.v]) {
            cout << "Graph contains a negative weight cycle\n";
            return;
        }
    }

    // Print distances
    for(int i = 0; i < V; i++) {
        cout << "Distance from " << src << " to " << i << " = ";
        if(dist[i] == 1e9) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
}

#include <iostream>

#include <vector>

using namespace std;

struct Edge {

int u, v, w;

};

void bellmanFord(int V, int src, vector<Edge>& edges) {

vector<int> dist(V, 1e9);

dist[src] = 0;

// Step 1: Relax edges V-1 times

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

for(auto e : edges) {

if(dist[e.u] != 1e9 && dist[e.u] + e.w < dist[e.v]) {

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

}

// Step 2: Check for negative weight cycle

for(auto e : edges) {

if(dist[e.u] != 1e9 && dist[e.u] + e.w < dist[e.v]) {

cout << "Graph contains a negative weight cycle\n";

return;

}

// Print distances

for(int i = 0; i < V; i++) {

cout << "Distance from " << src << " to " << i << " = ";

if(dist[i] == 1e9) cout << "INF\n";

else cout << dist[i] << "\n";

}

8️⃣ Graph Representation Used

Bellman–Ford typically uses an edge list:

This makes relaxing all edges straightforward.

9️⃣ Time & Space Complexity

Time Complexity

Space Complexity

Slower than Dijkstra, but more powerful.

🔟 Negative Weight Cycle Detection

A negative weight cycle is a cycle whose total weight is negative.

If such a cycle exists:

Shortest path is undefined
Distances can decrease forever

Bellman–Ford detects this reliably.

1️⃣1️⃣ Bellman–Ford vs Dijkstra

Feature	Bellman–Ford	Dijkstra
Negative weights	✅	❌
Negative cycle detection	✅	❌
Time complexity	O(VE)	O(E log V)
Speed	Slower	Faster

1️⃣2️⃣ Real-Life Applications

✔ Currency arbitrage detection
✔ Network routing (RIP protocol)
✔ Graphs with penalties / losses
✔ Financial modeling

Interview Questions (Bellman–Ford)

Q1. Why relax edges V−1 times?
👉 Longest simple path has at most V−1 edges

Q2. How to detect negative cycle?
👉 One extra relaxation pass

Q3. Why not always use Bellman–Ford?
👉 Too slow for large graphs

Final Summary

✔ Works with negative edge weights
✔ Detects negative weight cycles
✔ Uses edge relaxation
✔ Time complexity: O(V × E)
✔ Essential for advanced graph problems

DSA Bellman Ford Algorithm