Function bellmenFord

CPP/graphseries.cpp:521–559

shortest path in a graph with -ve weights

//shortest path in a graph with -ve weights 
void bellmenFord(int source){
	int n,m;
	cin>>n>>m;
	vector<node>edges;
	for(int i=0;i<m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		edges.push_back(node(x,y,w));
	}

	vector<int>distance(n,INT_MAX);
	distance[source]=0;

	//relaxing N-1 times every edge
	for(int i=0;i<=n-1;i++){
		for(auto it:edges){
			if(distance[it.v]>distance[it.u]+it.w){
				distance[it.v]=distance[it.u]+it.w;
			}
		}
	}

	int flag=0;
 
	//deceting negative cycle by relaxing one more time i.e Nth time
	for(auto it:edges){
		if(distance[it.v]>distance[it.u]+it.w){
			cout<<"Negative cycle";
			flag=1;
			break;
		}
	}

	if(flag==0){
		for(int i=0;i<n;i++){
			cout<<distance[i]<<" ";
		}
	}
}


int main()