单源最短路算法：SPFA 学习笔记
本帖最后由 RainPPR 于 2022-12-24 18:24 编辑# SPFA
SPFA（Shortest Path Faster Algorithm）算法是 Bellman-Ford 算法的队列优化算法，通常用于求含负权边的单源最短路径，以及判负权环。
复杂度：一般 O(m)，最坏 O(nm)。
## Bellman-Ford 的优化
### 先回顾下 Bellman-Ford 算法的思路
1. 迭代 n 次：`for i : 1 ~ n` 第 i 次操作表示：不超过 i 条边的最短距离
1. 枚举所有边：`for : ` `松弛操作`
2. `dist = min(dist, dist + w);`
### 如何优化
Bellman-Ford 算法，每次迭代所有边，来更新 `dist`（再此进行优化）
在 `dist = min(dist, dist + w);` 中，如果 dist 变小，则 `dist` 一定变小了（否则 dist 不会变）
这里用宽搜进行优化
## 算法思路
1. `queue ← 1`
2. while `queue` 不空
1. `t ← q.front;`
`q.pop();`
2. 更新 t 的所有出边：
`queue ← b;`（如果 b 不在队列里）
**详解见注释**
## 代码
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m; // n:点数 m:边数
int h, w, e, ne, idx;
int dist; // 从1号点走到每个点的最短距离
bool st; // 这个点是否在队列当中，避免重复存储
void add(int a, int b, int c)
{
e = b;
w = c;
ne = h;
h = idx++;
}
// 求出 1 号点到 n 号点的最短距离
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist = 0;
queue<int> q;
q.push(1);
st = true;
while (q.size())
{
int t = q.front();
q.pop();
st = false;
for (int i = h ; i != -1 ; i = ne)
{
int j = e;
if (dist > dist + w)
{
dist = dist + w;
if (!st)
{
q.push(j);
st = true;
}
}
}
}
if (dist == 0x3f3f3f3f)
return -2;
else
return dist;
}
int main()
{
// 初始化邻接表
memset(h, -1, sizeof(h));
// 输入
scanf("%d %d", &n, &m);
int a, b, c;
while (m--)
{
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
}
// SPFA
int t = spfa();
// 输出
if (t == -2)
printf("impossible\n");
else
printf("%d\n", t);
return 0;
}
```
# SPFA判断负环
抽屉原理
## 算法思路
`dist` 表示从 1 号点到 x 号点的最短距离；
`cnt` 表示从 1 号点到 x 号点（当前）最短路的边数；
当更新最短距离是更新 `cnt`。
若 `cnt ≤ n`，则一定经过了两个重复的点，即经过了一个环；而经过一个环，还是最短的，说明这个环是负环。
## 代码
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m; // n:点数 m:边数
int h, w, e, ne, idx;
int dist; // 从1号点走到每个点的最短距离
int cnt; // 从1号点走到每个点的最短距离所经过的边数
bool st; // 这个点是否在队列当中，避免重复存储
void add(int a, int b, int c)
{
e = b;
w = c;
ne = h;
h = idx++;
}
int spfa()
{
queue<int> q;
for (int i = 1 ; i <= n ; ++i)
{
q.push(i);
st = true;
}
while (q.size())
{
int t = q.front();
q.pop();
st = false;
for (int i = h ; i != -1 ; i = ne)
{
int j = e;
if (dist > dist + w)
{
dist = dist + w;
cnt = cnt + 1;
if (cnt >= n)
return true;
if (!st)
{
q.push(j);
st = true;
}
}
}
}
return false;
}
int main()
{
// 初始化邻接表
memset(h, -1, sizeof(h));
// 输入
scanf("%d %d", &n, &m);
int a, b, c;
while (m--)
{
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
}
// SPFA
int t = spfa();
// 输出
printf(t ? "Yes" : "No");
return 0;
}
``` 之前也学过这些，但是没有这么透彻 每天学个小知识
页:
[1]