最短路径（2）—— Bellman-Ford 算法 和SPFA 算法
- Bellman-Ford 算法 和SPFA 算法
前言
Dijkstra算法可以很好地解决无负权图的最短路径问题，但如果出现了负边权，Dijkstra算法就会失效。
按Dijkstra 算法来计算，最优解为A → B （d = -1）。但是实际最优解为：A → C→ B ( d = -6 )
为了更好地求解有负边权的最短路径问题，需要使用Bellman-Ford算法（简称BF算法）。和Dijkstra算法一样，Bellman-Ford算法可解决单源最短路径问题，但也能处理有负边权的情况。
Bellman-Ford 算法思路
给定一个有向图，若对于图中的某一条边（x,y,z），有d[y] <= d[x]+z成立，则称该边满足三角形不等式。若所有边都满足三角形不等式，则d数组就是所求最短路。
步骤1： 扫描所有边（x,y,z），若d[y] > d[x]+z ， 则用d[x]+ z 来更新d[y]。
步骤2：重复上述步骤，直到没有更新操作发生。
Bellman-Ford 算法的时间复杂度为O（nm）
- SPFA算法：队列优先的Bellman-Ford算法
实现方法：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值INF，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
这个队列避免了Bellman-Ford 算法中对不需要扩展的节点的冗余扫描，在稀疏图上运行效率较高，为O(km)级别，其中，k是一个较小的常数。但在稠密图或特殊构造的网格图上，该算法仍可能退化为O(nm)
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=100010;
const int INF=0x3f;
int n,m,s;
struct node{
int u,v,w,next;
}edge[N];
int head[N],cnt;
void add(int x,int y,int z){
edge[++cnt].u=x; edge[cnt].v=y; edge[cnt].w=z;
edge[cnt].next=head[x]; head[x]=cnt;
}
queue<int> q; //定义一个队列
int d[N],vis[N];
void spfa(int s) {
memset(d,INF,sizeof(d));
memset(vis,0,sizeof(vis));
d[s]=0; vis[s]=1;
q.push(s);
while(q.size()) {
int x=q.front(); q.pop(); //获取头元素，弹出
for(int i=head[x];i;i=edge[i].next) {
int v=edge[i].v , w=edge[i].w;
if(d[v] > d[x]+w) { //如果可以刷新原来的最短路径
d[v]=d[x]+w;
if(vis[v]==0) q.push(v), vis[v]=1; //如果没有被访问的则放入队列，然后标记已访问
}
}
}
}
int main() {
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
spfa(s);
for(int i=1;i<=n;i++) printf("%d ",d[i]);
return 0;
}
/*
3 3 1
1 2 -1
1 3 -1
3 2 -5
输出：0 -6 -1
*/ 结语
在NOI 2018的第一天第一题中，出题人卡了SPFA算法，导致100分变成60分，所以在没有负环、单纯求最短路径，不建议使用SPFA算法，而是用Dijkstra算法。
参考资料：
【洛谷日报#16】SPFA算法教学
SPFA算法