Bellman-Ford 与 SPFA 最短路算法

关于最短路的前置知识，我已经在最短路算法与 Floyd 中介绍过了。

Bellman-Ford 算法

算法思路

Bellman-Ford 最短路算法，类似于 Floyd 算法，是一种暴力扩展的算法，它的核心思想是对于一张 $n$ 个点，$m$ 条边的无向图，进行暴力扩展 $n$ 次，每次对于每一条边 $<u,v>$，用 $u$ 的 $dis$ 值对 $v$ 进行松弛。

要注意的是：初始化时，所有点的 $dis$ 值全部设为 $inf$，对于源点的 dis 值设为 $0$。

特点分析

时间复杂度：$O(n\times m)$，空间复杂度 $O(n+m)$。
优点：代码好写，易于理解；
缺点：效率较低，容易超时。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+6;
int u[N],v[N],w[N];
int dis[N];
void bellman_ford(int s,int n,int m) {
	memset(dis,0x3f,sizeof dis);
	dis[s]=0; //别忘了初始化
	for(int i=1;i<=n;++i) //n 次扩展操作
		for(int j=1;j<=m;++j) //对于每条边进行松弛
			if(dis[v[j]]>dis[u[j]]+w[j])
				dis[v[j]]=dis[u[j]]+w[j];
}
int main() {
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i)
		cin>>u[i]>>v[i]>>w[i];
	//for(int i=1;i<=m;++i) 无向图删掉注释
		//u[i+m]=v[i],v[i+m]=u[i],w[i+m]=w[i];
	bellman_ford(s,n,m);
	for(int i=1;i<=n;++i) cout<<dis[i]<<' ';
	return 0;
}

SPFA 优化

SPFA 算法，是一种基于 Bellman-ford 的优化，其全称是 Shortest Path Fast Algorithm，直译为“快速最短路算法”，快速一词，展现了它时间方面优于 Bellman-Ford 的一点。

在进行 Bellman-Ford 算法时，我们可以发现有很多冗余计算，如：

1. 在几次松弛操作之后，实际上就已经计算出了最短路径，而并不需要跑满 $m$ 编扩展。
2. 如果一条边连着的两个端点其最短路长度都为 $inf$，那么用 $inf$ 松弛 $inf$ 没有任何作用，只能增加冗余计算。
3. 如果一条边的两个端点在这轮扩展中都没有被更新，那么对于这条边进行松弛也是冗余的。

考虑优化冗余计算的情况，可以采用队列进行优化，对于本轮松驰过的点，加入队列进行计算，与 Dijkstra 不同的是，它采用的是队列进行松弛，而不是优先队列，所以一个点可能出队多次，每次出队，都需要进行松弛。

SPFA 算法大大减少了 Bellman-Ford 的冗余计算，它的最坏时间复杂度是 $O(nm)$，在普通图中时间复杂度是 $O(nk)$，$k$ 为一个不大的常数，但是，有些题目会故意构造特殊数据卡 SPFA 算法，所以，如果边权为正，建议使用 Dijkstra 算法。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+6, M = 2e5+6;
int hd[N],tot;
struct node {
	int to,wt,nx;
} eg[M<<1];
void adeg(int st,int ed,int wt) {
	eg[++tot]={ed,wt,hd[st]};
	hd[st]=tot;
}
int dis[N],len[N];
bool spfa(int s,int n) {
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	queue<int> q;
	q.push(s);
	while(q.size()) {
		int st=q.front();
		q.pop();
		for(int i=hd[st];i;i=eg[i].nx) {
			int to=eg[i].to,wt=eg[i].wt;
			if(dis[to]>dis[st]+wt) {
				dis[to]=dis[st]+wt;
				len[to]=len[st]+1;
				if(len[to]>n) return 1;
				q.push(to);
			}
		}
	} return 0;
}
int main() {
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i) {
		int u,v,w;
		cin>>u>>v>>w;
		adeg(u,v,w);
		//adeg(v,u,w); 无向图把注释删掉
	}
    bool flag=spfa(s,n);
    if(flag) cout<<"No solution!";
	else for(int i=1;i<=n;++i) cout<<dis[i]<<' ';
	return 0;
}