Bellman-Ford 与 SPFA 最短路算法

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

Bellman-Ford 算法

算法思路

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

要注意的是:初始化时,所有点的 disdis 值全部设为 infinf,对于源点的 dis 值设为 00

特点分析

时间复杂度:O(n×m)O(n\times m),空间复杂度 O(n+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. 在几次松弛操作之后,实际上就已经计算出了最短路径,而并不需要跑满 mm 编扩展。
  2. 如果一条边连着的两个端点其最短路长度都为 infinf,那么用 infinf 松弛 infinf 没有任何作用,只能增加冗余计算。
  3. 如果一条边的两个端点在这轮扩展中都没有被更新,那么对于这条边进行松弛也是冗余的。

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

SPFA 算法大大减少了 Bellman-Ford 的冗余计算,它的最坏时间复杂度是 O(nm)O(nm),在普通图中时间复杂度是 O(nk)O(nk)kk 为一个不大的常数,但是,有些题目会故意构造特殊数据卡 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;
}
赞赏