目录
一、概念
二、思路
三、spfa求最短路
在阅读本文前请先食用：
【算法】Bellman-Ford单源最短路径算法（附动图）-CSDN博客文章浏览阅读366次，点赞16次，收藏14次。算法学习笔记之Bellman-Ford单源最短路径算法https://blog.csdn.net/Eristic0618/article/details/143207783
一、概念
- spfa算法是对Bellman-Ford单源最短路算法的优化
- Bellman-Ford算法每次循环都要遍历所有的边，只有dist[a]+w < dist[b]节点的dist值才会被更新，很多情况下遍历了某条边后节点的dist值并没有被更新
- 可以发现，在Bellman-Ford算法中，只有某个节点的前继节点被更新，这个节点的dist值才可能被更新
- 因此，spfa算法基于宽搜思想对Bellman-Ford进行优化，将被更新的节点加入队列
二、思路
spfa算法的核心思路：用被更新的节点去更新其他的节点
（记好节点编号，后面为了方便展示将节点编号替换为节点的dist值）
首先将源节点入队
当队列不为空时，取出队头节点并遍历其出边，更新其他节点，并将被更新的节点入队
循环上一步
当遍历2号节点的出边时，3号节点被更新，但队列中已经存在3号节点，所以无需再次入队
为了维护队列中节点的唯一性，我们需要一个check数组
当队列为空时得出最优解
三、spfa求最短路
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;const int N = 100010;int n, m, dis[N];
int e[N], h[N], w[N], ne[N], idx;
bool check[N]; //维护队列，使队列中节点不重复int spfa()
{//初始化dist数组memset(dis, 0x3f, sizeof dis);dis[1] = 0;queue<int> q; //宽搜核心：队列q.push(1); //将源节点加入队列while(q.size()) //当队列非空{int t = q.front(); //取出队头节点q.pop(); //节点出队check[t] = false; //修改check数组for(int i = h[t];i != -1;i = ne[i]) //遍历节点所有出边{int j = e[i]; //j为有向边指向的节点if(dis[j] > dis[t] + w[i]) // 更新为更短距离，将对应点入队{dis[j] = dis[t] + w[i];if(!check[j]) //若队列中不存在该节点{q.push(j); //节点入队check[j] = true; //修改check数组}}}}return dis[n];
}void add(int a, int b, int c) //构建邻接表
{e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}int main()
{memset(h, -1, sizeof h);cin >> n >> m;for(int i = 1;i <= m;i++) //构建邻接表{int a, b ,c;cin >> a >> b >> c;add(a, b, c);}int t = spfa(); //spfa算法if(t == 0x3f3f3f3f) cout << "impossible";else cout << t;return 0;
}完.
