Detect negative cycle in Bellman-Ford Algorithm

Bellman ford algorithm is used to find the single shortest path in a graph with negative edge weight(but it should not contain negative cycles).

In this article we will discussed about how to detect negative cycle in a Bellman Ford algorithm?

What is a negative cycle? A negative cycle in a weighted directed graph is a cycle whose sum of all weights is negative .

Lets us understand through example:

The total sum along edges is 4 and is positive and hence it does not contain negative cycle.

The total sum along edges is -4 and hence it contain a negative cycle.

Algorithm to detect whether a graph contains a negative cycle or not

1.We will make a distance array and fill it with INFINITY value and assign the initial source value distance[0]=0;

2.We will relax all the edges of the graph by loop n-1 times.

3.We will perform an Nth loop iteration to check whether it contains negative cycle or not.

1. If there exist a better path to reach vertex v, then we update the distance and value of v.

Lets us understand about relaxing edges

Consider an edge u->v where u is initial vertex and v is the end vertex. Relaxing edges (U,V)means to find the shorter path to reach v when considering our edges from u->v.

relax(u,v)

if v(distance) > u(distance) + w(u,v)

then

v(distance) = u(distance) + w(u,v)

v.p = u>

where:

v(distance)=Distance from source(0) to vertex v

u(distance)=Distance from source(0) to vertex u

w(u,v)=weight of edges u->v

v.p=predecessor of v

Let us understand through figure:-

Why we are performing Nth loop?

After completing the (N-1)th iteration we will get the distance array and while performing Nth operation if there is no change in the distance array then we can say graph has no negative cycle and we can print the cycle and find the shortest path. Otherwise the graph has an negative cycle and we cannot find the shortest path.

INPUT

4 5

0 1 5

0 2 4

1 3 3

2 1 -6

3 2 2

0

OUTPUT

negative cycle

INPUT

6 7

3 2 6

5 3 1

0 1 5

1 5 -3 1 2 -2

3 4 -2

2 4 3

0

OUTPUT

0 0

1 5

2 3

3 3

4 1

5 2

CODE

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

 struct node{

int u; 
int v;
int wt;
node(int start,int end,int weight)
{
    u=start;
    v=end;
    wt=weight;
}
};

int main()
{
    int n,m;
    cin>>n>>m;
    vector<node>edge;
    int u,v,wt;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>wt;
        edge.push_back(node(u,v,wt));
    }
    int source;
    cin>>source;
    vector<int>dist(n,1000000);
    dist[source]=0;
    for(int i=1;i<=n-1;i++)
    {
        for(auto it:edge)
        {
            if(dist[it.v]>dist[it.u]+it.wt)
            {
              dist[it.v]=dist[it.u]+it.wt;
            }
        }
    }
    bool check=false;
    for(auto it:edge)
    {
        if(dist[it.v]>dist[it.u]+it.wt)
        {
            check=true;
            break;
        }
    }
    if(check)
    {
        cout<<"Negative cycle"<<endl;
    }
    else{
        for(int i=0;i<n;i++)
        {
            //print the last value in distance array if it does  not contain cycle
            cout<<i<<" "<<dist[i]<<endl;
        }
    }

}

Time complexity: O(V*E) where V is the number of vertices and E is the total number of edges in an graph