贝尔曼福特算法

//Bellman_ford
#include<iostream>
using namespace std;
struct Edge{
	int v,e,weight;
}a[1000];
int dist[1000];
int node,edge,source,i,j;
bool Bellman_ford()
{
    for(i=2;i<=node;i++)
	{
		for(j=1;j<=edge;j++)
		{
			if(dist[a[j].e]>dist[a[j].v]+a[j].weight)
			   dist[a[j].e]=dist[a[j].v]+a[j].weight;
		}
	}
	for(j=1;j<=edge;j++)
	{
		if(dist[a[j].e]>dist[a[j].v]+a[j].weight)
		return false;
	}	
	return true;
}
int main()
{
	cin>>node>>edge>>source;
	for(i=1;i<=edge;i++)
	dist[i]=9999;
	for(i=1;i<=edge;i++)
	{
	    cin>>a[i].v>>a[i].e>>a[i].weight;
	    if(source==a[i].v)
	    {
	    	dist[source]=0;
	    	dist[a[i].e]=a[i].weight;
	    }
	}
	if(Bellman_ford())
	{
		for(i=1;i<=edge;i++)
		cout<<dist[i]<<endl;
	}
	return 0;
}
/*
input :
5 5 1
1 2 10
2 3 50
3 5 10
1 5 100
1 4 30
output:
0
10
60
30
70
*/
/*
author Sunshine_小高 
*/

贝尔曼福特算法,布布扣,bubuko.com

贝尔曼福特算法

原文：http://blog.csdn.net/guanjungao/article/details/21738925