Bellman-Ford Algorithm

Concept

Bellman-Ford finds the shortest path from a single source to all other nodes, even when edges have negative weights. It relaxes all edges V-1 times. If any edge can still be relaxed after V-1 iterations, a negative cycle exists.

When to Use

  • ▸Shortest path with negative edge weights
  • ▸Detecting negative weight cycles
  • ▸When Dijkstra can't be used (negative weights)
  • ▸Problems involving currency exchange or arbitrage detection

Intuition

Think of it as a rumor spreading through a network. In each round, every person (edge) tells their neighbors about the best distance they know. After V-1 rounds, the shortest distances have propagated through the longest possible path. If distances still improve in round V, it means there's a loop that keeps making things cheaper — a negative cycle.

Complexity

Time
O(V * E)
Space
O(V + E)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m, s;
    cin >> n >> m >> s;

    vector<pair<pair<int, int>, int>> edges;

    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({{u, v}, w});
    }

    const int inf = 1e9+7;
    vector<int> dist(n, inf);
    dist[s] = 0;

    for(int i = 0; i < n-1; i++){
        bool updated = false;

        for(auto &e : edges){
            int u = e.first.first;
            int v = e.first.second;
            int w = e.second;

            if(dist[u] != inf && dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                updated = true;
            }
        }

        if(!updated) break;
    }

    bool negativeCycle = false;
    for(auto &e : edges){
        int u = e.first.first;
        int v = e.first.second;
        int w = e.second;

        if(dist[u] != inf && dist[u] + w < dist[v]){
            negativeCycle = true;
            break;
        }
    }

    if(negativeCycle){
        cout << "Negative Cycle";
    }
    else{
        for(int i = 0; i < n; i++){
            cout << dist[i] << " ";
        }
    }

    return 0;
}

// Sample Input:
// 5 8 0
// 0 1 6
// 0 2 7
// 1 2 8
// 1 3 5
// 1 4 -4
// 2 3 -3
// 2 4 9
// 3 4 7
//
// Sample Output:
// 0 6 7 4 2