» » Bellman Ford

Bellman Ford

   4:51 PM       

 
vector < pii > M[mx];
int d[mx];
bool bellman_ford(int s,int n){
	int i,u,j,sz,v,w;
	bool done = false;
	for(i=0;i<n;i++)d[i] = inf;
	d[s] = 0;
	for(i=0;i<n && !done;i++){
		done = true;
		for(u=0;u<n;u++){
			sz = M[u].size();
			for(j=0;j<sz;j++){
				v = M[u][j].first;
				w = M[u][j].second;
				if(d[v] > (d[u] + w)){
					d[v] = d[u] + w;
					done = false;
				}
			}
		}
	}
	return done;
}