Bellman-Ford算法思路详解及SPFA算法简介

#include
using namespace std;

const int MN=1005,INF=0x3f3f3f3f;
int d[MN],ans,n,m,en,s;
struct Edge{
	int u,v,w; //u,v为顶点，w为边权
}ed[MN]; //边集数组，不关心边之间的对应关系，没有定义nxt模拟指针字段
/*该图有n个结点，m条边*/
bool Bellman(int s){
	memset(d,0x3f,sizeof(d)); //单源最短路记录数组初始化为INF
	d[s]=0; //源点s，最短路为0
	for(int i=1;id[tu]+tw) //松弛检测
				d[tv]=d[tu]+tw; 
		}
	for(int j=1;j<=m;++j)
	{//验证是否有环，如果n次松弛之后，还可以松弛，就是有环
		int tu=ed[j].u,tv=ed[j].v,tw=ed[j].w;
		if(d[tv]>d[tu]+tw)
			return 0; //有环返回0
	}
	return 1;//无环返回1
}

 Bellman-Ford 算法优化优化：

循环的提前退出：

　　在实际操作中，贝尔曼-福特算法经常会在未达到 |V| - 1 次前就出解，|V| -1 其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。【类似于冒泡排序的优化】

      由读者自行完成实现，可以用bool变量每轮是否有松弛操作。

二、SPFA：Bellman-Ford 算法的队列优化实现

是一个用于求解有向带权图单源最短路径的改良的贝尔曼-福特算法(当然也可以通过将每条边换为两条逆向的边来用于无向图)。这一算法被认为在随机的稀疏图上表现出色，并且极其适合带有负边权的图。然而SPFA在最坏情况的时间复杂度与Bellman-Ford算法相同，因此在非负边权的图中仍然最好使用Dijkstra。

原理：

　　基于Bellman-Ford之外，再可以确定，松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。

优化：

　　SPFA算法的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。

       我们注意到其与Dijkstra很像，

       一方面，优先队列替换成普通的FIFO队列，

       而另一方面，一个节可以多次进入队列点。

SPFA 代码模板：习题：香甜的黄油 【点击链接打开】

//【例4-6】香甜的黄油——一本通入门篇练习题：
#include
using namespace std;
const int INF=0x3f3f3f3f;
int n,p,c,a[501],hd[801],en,ds[801],tot,ans=INF;
bool ext[801];
struct Edge{
	int to,nxt,dis;
}ed[2902]; 

void addEdge(int from,int to,int dis){
	en++;
	ed[en].dis=dis;
	ed[en].to=to;
	ed[en].nxt=hd[from];
	hd[from]=en;
}

void spfa(int s){	
	queue qe;
	qe.push(s);
	ext[s]=1; //起点标记在队列中
	ds[s]=0;
	while(!qe.empty()){
		int qf=qe.front();
		qe.pop();
		ext[qf]=0; //对头结点出队后，标记为不在队列中
		for(int j=hd[qf];j;j=ed[j].nxt){
			int qt=ed[j].to,qw=ed[j].dis;
			
			if(ds[qt]>ds[qf]+qw){
				ds[qt]=ds[qf]+qw;
				
				if(!ext[qt]){ //不在队列中的结点才需要再次入队
					ext[qt]=1;
					qe.push(qt);
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>p>>c;
	for(int i=1;i<=n;++i)
		cin>>a[i];		
	
	for(int i=0;i>u>>v>>d;
		addEdge(u,v,d);
		addEdge(v,u,d);
	}
	for(int i=1;i<=p;++i){
		memset(ds,0x3f,sizeof(ds));
		memset(ext,0,sizeof(ext));
		spfa(i);  //调用p次spfa()
		tot=0;
		for(int i=1;i<=n;++i)
			tot+=ds[a[i]];
		ans=min(ans,tot);
	}
	cout<