单源最短路之——优化的Bellman-Ford算法

Bellman-Ford用来解决单源最短路径问题，相比Dijkastra，它的限制更少：边权值可以为负。同时，还能检测出负环（正环）。但普通的Bellman-Ford时间复杂度高于Dijkastra，因此更多人喜欢使用SPFA。但经过优化的Bellman-Ford算法，时间复杂度大大降低，可以相比于SPFA。

这里推荐：http://www.cppblog.com/apple365/archive/2008/11/27/67943.html，这里有详细Bellman-Ford原理及其优化过程。

 

#include <iostream>
using namespace std;
const double MAX = -1000000.0;
typedef struct
{
	int v1;
	int v2;
	double rate;
	double comm;
}Edge;
Edge e[201];
int n;				//货币种数
int m;				//银行总数
int s;				//初始货币类型
double v;			//初始财产
double d[101];		//源点s到各点的最小距离

int main()
{
	bool flag;
	int i,j,p,q,num;
	cin>>n>>m>>s>>v;
	for(i = 1,num = 0; i <= m; i++)
	{
		cin>>p>>q;
		num++;
		e[num].v1 = p;
		e[num].v2 = q;
		cin>>e[num].rate;
		cin>>e[num].comm;
		num++;
		e[num].v1 = q;
		e[num].v2 = p;
		cin>>e[num].rate;
		cin>>e[num].comm;
	}
	for(i = 1; i <= n; i++)
		d[i] = MAX;
	d[s] = v;
	/*优化的bellman-ford
	从第一次到第n-1次循环中，若有一次所有的边都没有松弛，以后所有边也不需要松弛，显然算法可以终止！
	bellman-ford算法在做完n-1次之后，若不存在正环，肯定会收敛，即第n次跳出（此时还要判断d[s]的值是否增加）。再做一次，
	即到第n次还满足松弛条件，说明存在正环*/
	for(i = 1; i <= n; i++)
	{
		flag = false;
		for(j = 1; j <= num; j++)
		{
			if(d[e[j].v1] != MAX && (d[e[j].v1] - e[j].comm)*e[j].rate > d[e[j].v2])	//松弛条件
			{
				d[e[j].v2] = (d[e[j].v1] - e[j].comm)*e[j].rate;
				flag = true;
			}
		}
		if(!flag) break;
	}
	if(i == n + 1)
		cout<<"YES\n";
	else
	{
		if(d[s] > v)
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}

 

参加poj1860,3259