关于最短路的前置知识,我已经在最短路算法与 Floyd 中介绍过了。
Bellman-Ford 算法
算法思路
Bellman-Ford 最短路算法,类似于 Floyd 算法,是一种暴力扩展的算法,它的核心思想是对于一张 个点, 条边的无向图,进行暴力扩展 次,每次对于每一条边 ,用 的 值对 进行松弛。
要注意的是:初始化时,所有点的 值全部设为 ,对于源点的 dis 值设为 。
特点分析
时间复杂度:,空间复杂度 。
优点:代码好写,易于理解;
缺点:效率较低,容易超时。
代码
#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 算法时,我们可以发现有很多冗余计算,如:
- 在几次松弛操作之后,实际上就已经计算出了最短路径,而并不需要跑满 编扩展。
- 如果一条边连着的两个端点其最短路长度都为 ,那么用 松弛 没有任何作用,只能增加冗余计算。
- 如果一条边的两个端点在这轮扩展中都没有被更新,那么对于这条边进行松弛也是冗余的。
考虑优化冗余计算的情况,可以采用队列进行优化,对于本轮松驰过的点,加入队列进行计算,与 Dijkstra 不同的是,它采用的是队列进行松弛,而不是优先队列,所以一个点可能出队多次,每次出队,都需要进行松弛。
SPFA 算法大大减少了 Bellman-Ford 的冗余计算,它的最坏时间复杂度是 ,在普通图中时间复杂度是 , 为一个不大的常数,但是,有些题目会故意构造特殊数据卡 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;
}