bellman ford algorithm
//It is an algorithm to detect negative cycle in a graph as well as can we used to find the shortest distance from source
#include<bits/stdc++.h>
using namespace std;
struct node
{
int u,v,wt;
node(int first,int second ,int weight)
{
u=first;
v=second;
wt=weight;
}
};
int main()
{
int vertex,edges;
cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
cin>>vertex>>edges;
vector<node>adj;
cout<<"ENTER THE LINKS:"<<endl;
int a,b,w;
for(int i=0;i<edges;i++)
{
cin>>a>>b>>w;
adj.push_back(node(a,b,w));
}
int src;
cout<<"ENTER THE SOURCE"<<endl;
cin>>src;
int large=100000;
vector<int>dist(vertex,large);
dist[src]=0;
for(int i=1;i<=vertex-1;i++)
{
for(auto it:adj)
{
if(dist[it.u]+it.wt<dist[it.v])
{
dist[it.v]=dist[it.u]+it.wt;
}
}
}
int flag=0;
for(auto it:adj)
{
if(dist[it.u]+it.wt<dist[it.v])
{
cout<<"NEGATIVE CYCLE DETECTED:"<<endl;
flag=1;
break;
}
}
if(!flag)
{
for(int i=0;i<vertex;i++)
{
cout<<i<<" "<<dist[i]<<endl;
}
}
return 0;
}