🥂前言
前面，我们分别介绍了Dijkstra算法（【最短路算法】一篇文章彻底弄懂Dijkstra算法|多图解+代码详解）和Bellman-Ford算法
【最短路算法】第二弹：一文弄懂Bellman-Ford(贝尔曼福特算法)
前者用于求单源、正权边最短路问题，后者用于求单源、带负权边最短路问题。通过对Bellman-Ford算法讲解，我们知道，Bellman-Ford算法美中不足的一点在于时间复杂度是O(nm)，时间复杂度过高。
今天，我们学习的spfa算法，优化了Bellman-Ford算法，时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m 表示边数。
🍚一、算法思想
在讲具体算法思想之前，我们来仔细探讨一下，优化的点在哪里？
Bellman-ford算法慢，就慢在，其实在后面遍历时，每次迭代都要遍历所有边。前面我们说到过，迭代次数代表从源点出发，经过不超过迭代次数的边数，所经过的顶点的dist都是准确的，确定的。但是在后面迭代中，又重复去遍历这些边，其实是没有必要的。
因为判断一个点的松驰条件为:假设边为a→bdist[b] = min (dist[b], dist[a]+w),当dist[a]（a其实不是某一个点，代表的是从a指向b的边的一群顶点）都一直没有更新，dist[b]当然也不会更新，确定好了dist[b]，在后面遍历中，dist[b] = min (dist[b], dist[a]+w)完全没有必要进行。那如何减少这一无意义操作呢？
核心就是，我们只对其dist有更新的顶点进行松驰！（注意，这样一来，spfa当然就不会有bellman-Ford算法的那种迭代次数的意义存在！）
spfa，利用宽搜思想，使用队列为数据结构，优化了这一点。，优化了这一点。
-
📍首先，将dist变小的即有被更新的点入队（因为它的更新，一般会带来其他点的更新）
-
📍取出队列元素，并将其弹出
-
📍对该元素的出边元素进行遍历&松驰
-
📍如果有元素松驰成功（dist更新，也就是变小了），那么该元素也入队
算法模板如下：（from acWing)
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
🌽二、spfa求最短路
acWing 851. spfa求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出
impossible。数据保证不存在负权回路。
输入格式第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出impossible。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;//邻接表存储图
int dist[N];
bool st[N];//标记节点是否在队列中
//构建边
void add(int a,int b, int c){
e[idx] = b,w[idx] = c, ne[idx] = h[a],h[a] = idx++;
}
void spfa(){
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
queue<int> q;//队列
q.push(1);//因为dist[1] 从0x3f3f3f3f松驰为了0，加入队列
st[1] = true;
while(q.size()){//while队列不空
int t = q.front();//取出队头元素，由该点更新其出边点
q.pop();//出队
st[t] = false;
//遍历t点的出边点
for(int i = h[t]; i!=-1; i = ne[i]){
int j = e[i];
//判断该点是否可以进行松驰操作并松驰
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] +w[i];
if(!st[j]){//对该点做了更新，把该点也要入队
q.push(j);
st[j] = true;
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
//！h[N]数组要先初始化
memset(h,-1,sizeof(h));
for(int i = 0; i < m; i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
spfa();
if(dist[n] == 0x3f3f3f3f) puts("impossible");
else printf("%d\n",dist[n]);
return 0;
}
🥘三、spfa判断负权回路
- spfa判断负环
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出
Yes，否则输出No。数据范围
1≤n≤2000, 1≤m≤10000, 图中涉及边长绝对值均不超过 10000。
🛫思路
统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则也说明存在负环
1、dist[x] 记录虚拟源点到x的最短距离
2、cnt[x] 记录当前x点到虚拟源点最短路的边数，初始每个点到虚拟源点的距离为0，只要他能再走n步，即cnt[x] >= n，则表示该图中一定存在负环，由于从虚拟源点到x至少经过n条边时，则说明图中至少有n + 1个点，表示一定有点是重复使用
3、若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少，因此进行对该点j进行更新，并且对应cnt[j] = cnt[t] + 1,往前走一步
🛫详细注释题解
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 10010;
int n,m;
int h[N],w[M],e[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];
void add(int a,int b,int c){
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
//spfa算法判断负权回路
bool spfa(){
queue<int> q;
//将所有顶点都入队
for(int i = 1; i <= n; i ++){
st[i] = true;
q.push(i);
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof(h));
while(m --){
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}
🛫注意点
- 为什么不用初始化dist[N]? 因为负环的存在，所以即使每个点距离虚拟原点距离为0，负权回路的存在就可以更新某个点的dist为更小的值.这题是判断，只要有这个变小（松驰）趋势就Ok，并不是求最短路
- 注意：该题是判断是否存在负环，并非判断是否存在从1开始的负环，因此需要将所有的点都加入队列中，更新周围的点.换句话来说，**从哪个点出发并不重要，重要的是是否有负环！**一定要将所有点入队我认为是因为图可能会不连通，如果负环是在和1这个点不连通的部分（可能图中存在负环，但是从一号点到不了），就无法查到，所以要将所有点都入队！遍历所有点，肯定能遍历到有负环的回路，只要有负环,dist就会更新，顶点就会接着入队，cnt也接着增加！
- 对比：以 S 点为源点跑 Bellman-Ford 算法时，如果没有给出存在负环的结果，只能说明从 S 点出发不能抵达一个负环，而不能说明图上不存在负环。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/142441.html
