Bellmon_Ford算法详解

Bellmon_Ford算法简述： 这个算法求最短路最大的特点是可以处理负边，理解这个算法的关键在于对于二重循环的理解，首先看第2重循环：for(int j=1;j<=m;j++)这层循环主要是对m条边进行松弛(relax)操作，理解的关键在于， 第k次对m条边进行一遍松弛操作，便可以确定经过k条边可到达顶点的最短路径，注意到有的时候或许在前k次便已经得到了这个顶点的最短路，但是只有经过k次松弛才能够确定它的最短路，这主要和图的数据有关。

#include  
#include  
#include  
using namespace std;
const int maxm=300;//定义最大边数
int n,m,u[maxm],v[maxm],w[maxm];
int dist[100];//最短距离数组
const int inf=99999999;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
	for(int i=1;i<=n;i++)
		dist[i]=inf;
	dist[1]=0;
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=m;j++)
			if(dist[v[j]]>dist[u[j]]+w[j])
				dist[v[j]]=dist[u[j]]+w[j];
	for(int i=1;i<=n;i++)
		printf("%d ",dist[i]);
	return 0;
}

下面再补充对Bellmon_Ford算法的队列优化，这种算法也称为SPFA算法，基本思想是：首先将源点s入队列，接着每一次将队首节点取出，将其与相临边进行松弛操作。

#include  
#include  
#include  
#include  
#include  
using namespace std;
const int maxn=5000;
struct Edge//边
{
	int u,v,d;
	Edge(){}
	Edge(int u,int v,int d)
	{
		this->u=u,this->v=v,this->d;
	}
};
struct Bellmon_Ford
{
	int n,m,d[maxn],par[maxn];
	bool inque[maxn];
	vector G[maxn];
	vector edges;
	void init(int n)
	{
		this->n=n;
		for(int i=0;i<=n;i++)
			G[i].clear();
		edges.clear();
	}
	void AddEdge(int u,int v,int d)
	{
		edges.push_back(u,v,d);
		m=edges.size();
		G[u].push_back(m-1);
	}
	bool bellmon_ford(int s)
	{
		memset(cnt,0,sizeof(cnt));
		memset(inque,false,sizeof(inque));
		memset(d,0x7f7f7f,sizeof(d));
		d[s]=0;
		cnt[s]++;
		inque[s]=true;
		queue que;
		que.push(s);
		while(!que.empty())
		{
			int u=que.front();
			que.pop();
			inque[u]=false;
			for(int i=0;id[u]+e.d)
				{
					d[e.v]=d[e.u]+e.d;
					par[e.v]=e.u;
					if(!inque[e.v])
					{
						que.push(e.v);
						if(++cnt[e.v]>n)
						{
							return true;
						}
					}
				}
			}
		}
		return false;
	}
};