bellman_ford.cpp

// Bellman ford on weighted GRAPH
// O(n*m) time complexity
// GRAPH's edge list representation
// vertices start from 1 onwards
// can detect negative cycle in graph
#include <bits/stdc++.h>
using namespace std;
const int INF=1e7;

int main() {
	int node,edge;
	cout<<"enter no of vertices & edges\n";
	cin>>node>>edge;
	vector<tuple<int,int,int>>adj_edges;
	cout<<"enter adjacent nodes & weight between them";
	for(int i=0;i<edge;i++){
	    int a,b,w;
	    cin>>a>>b>>w;
	    a--;
	    b--;
	    adj_edges.push_back(make_tuple(a,b,w));
	}
	
	int distance[node];
	for(int i=0;i<node;i++){
	    distance[i]=INF;
	}
	
	int source;
	cout<<"enter source from where u have to calculate min distance\n";
	cin>>source;
	distance[source-1]=0;
	for(int i=0;i<edge-1;i++){
	    for(auto e: adj_edges){
	        int a,b,w;
	        tie(a,b,w)=e;
	        distance[b]=min(distance[a]+w,distance[b]);
	    }
	}
	cout<<"distance of nodes from source "<<source<<"\n";
	for(int i=0;i<node;i++){
	    cout<<i+1<<" : "<<distance[i]<<"unit\n";
	}
	return 0;
}