Bellman–Ford & negative cycles

Allow negative weights by repeatedly relaxing every edge. A reachable negative cycle means some distances have no finite minimum.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. A shortest simple path uses at most n−1 edges.
2. Run n−1 full relaxation passes, stopping early if nothing changes.
3. A further possible relaxation detects a negative cycle reachable from the source.
4. To determine affected targets, propagate from vertices improved in the extra pass.
5. After n−1 passes every shortest simple path has enough edge relaxations. A further reachable improvement certifies a negative cycle; the explicit input bounds keep intermediate sums within long long.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: After n−1 passes every shortest simple path has enough edge relaxations. A further
// reachable improvement certifies a negative cycle; the explicit input bounds keep intermediate sums
// within long long.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
struct Edge{
    int u,v,w;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,source;
    cin>>n>>m>>source;
    vector<Edge>edges(m);
    for(Edge&edge:edges){
        cin>>edge.u>>edge.v>>edge.w;
    }
    vector<long long>d(n+1,(1LL<<62));
    d[source]=0;
    for(int pass=1;pass<n;++pass){
        bool changed=false;
        for(auto e:edges){
            if(d[e.u]!=(1LL<<62)&&d[e.v]>d[e.u]+e.w){
                d[e.v]=d[e.u]+e.w;
                changed=true;
            }
        }
        if(!changed){
            break;
        }
    }
    bool negativeCycle=false;
    for(auto e:edges){
        if(d[e.u]!=(1LL<<62)&&d[e.v]>d[e.u]+e.w){
            negativeCycle=true;
        }
    }
    if(negativeCycle){
        cout<<"NEGATIVE CYCLE\n";
        return 0;
    }
    for(int vertex=1;vertex<=n;vertex++){
        if(vertex>1){
            cout<<' ';
        }
        if(d[vertex]==(1LL<<62)){
            cout<<"INF";
        }
        else{
            cout<<d[vertex];
        }
    }
    cout<<'\n';
}

Complexity analysis

O(VE) time, O(V) distance space.

Example input and output

Read n m source and m directed edges a b weight. Require 1≤n≤2000, m≤10000 and |weight|≤10^6. Print NEGATIVE CYCLE if one is reachable from source; otherwise print distances, using INF for unreachable labels.

Input

4 4 1
1 2 5
1 3 2
3 2 -4
2 4 3

Output

0 -2 2 1

The path 1→3→2 has cost -2 and continuing to 4 has cost 1. No reachable negative cycle exists.

Practical applications

Use Bellman–Ford for negative edges and reachable negative-cycle detection when O(nm) work is acceptable.

Check your understanding

How many passes suffice without reachable negative cycles?

Put it into practice

Find distances in a directed graph with negative edges and detect a reachable negative cycle.