SPFA 算法介绍
适用范围: 给定的图存在负权边, 这时类似 Dijkstra 等算法便没有了用武之地, 而 Bellman-Ford 算法的复杂度又过高, SPFA 算法便派上用场了. 我们约定有向加权图 G 不存在负权回路, 即最短路径一定存在. 当然, 我们可以在执行该算法前做一次拓扑排序, 以判断是否存在负权回路, 但这不是我们讨论的重点.
SPFA 算法是求解单源最短路径问题的一种算法, 由理查德·贝尔曼 (Richard Bellman) 和 莱斯特·福特 创立的. 有时候这种算法也被称为 Moore-Bellman-Ford 算法, 因为 Edward F. Moore 也为这个算法的发展做出了贡献. 它的原理是对图进行 $V-1$ 次松弛操作, 得到所有可能的最短路径. 其优于 Dijkstra 算法的方面是边的权值可以为负数, 实现简单; 缺点是时间复杂度过高, 高达 $O(VE)$. 但算法可以进行若干种优化, 提高了效率.
SPFA(Shortest Path Faster Algorithm), 图的存储方式为邻接表, 是 Bellman-Ford 算法的一种队列实现, 减少了不必要的冗余计算. 算法大致流程是用一个队列来进行维护. 初始时将源加入队列. 每次从队列中取出一个元素, 并对所有与他相邻的点进行松弛, 若某个相邻的点松弛成功, 则将其入队. 直到队列为空时算法结束. 它可以在 O(kE) 的时间复杂度内求出源点到其他所有点的最短路径, 可以处理负边. SPFA 在形式上和 BFS 非常类似, 不同的是 BFS 中一个点出了队列就不可能重新进入队列, 但是 SPFA 中一个点可能在出队列之后再次被放入队列, 也就是一个点改进过其它的点之后, 过了一段时间可能本身被改进, 于是再次用来改进其它的点, 这样反复迭代下去.
判断有无负环: 如果某个点进入队列的次数超过 $V$ 次则存在负环 (SPFA 无法处理带负环的图).
SPFA 算法有两个优化算法 SLF 和 LLL:
- Small Label First 策略, 设要加入的节点是 $j$, 队首元素为 $i$, 若 $dist(j)<dist(i)$, 则将 $j$ 插入队首, 否则插入队尾.
- Large Label Last 策略, 设队首元素为 $i$, 队列中所有 $dist$ 值的平均值为 $x$, 若 $dist(i)>x$ 则将 $i$ 插入到队尾, 查找下一元素, 直到找到某一 $i$ 使得 $dist(i) \le x$, 则将 $i$ 出对进行松弛操作.
引用网上资料, SLF 可使速度提高 15 ~ 20%; SLF + LLL 可提高约 50%. 在实际的应用中 SPFA 的算法时间效率不是很稳定, 为了避免最坏情况的出现, 通常使用效率更加稳定的 Dijkstra 算法.
实现
SPFA 是对 Bellman-Ford 的优化实现, 可以使用队列进行优化, 也可以使用栈进行优化.
通常情况下复杂度为 $O(k*m)$, $k$ 一般为 $4$ 到 $5$, 最坏情况下仍为 $O(n * m)$, 当数据为网格图时, 复杂度会从 $O(k*m)$ 退化为 $O(n*m)$.
判断有无负环: 如果某个点进入队列的次数超过 N 次则存在负环 (SPFA 无法处理带负环的图)
代码:
class Solution {
int N = 110, M = 6010;
// 邻接表
int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
int[] dist = new int[N];
// 记录哪一个点「已在队列」中
boolean[] vis = new boolean[N];
int INF = 0x3f3f3f3f;
int n, k, idx;
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx;
w[idx] = c;
idx++;
}
public int networkDelayTime(int[][] ts, int _n, int _k) {
n = _n; k = _k;
// 初始化链表头
Arrays.fill(he, -1);
// 存图
for (int[] t : ts) {
int u = t[0], v = t[1], c = t[2];
add(u, v, c);
}
// 最短路
spfa();
// 遍历答案
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, dist[i]);
}
return ans > INF / 2 ? -1 : ans;
}
void spfa() {
// 起始先将所有的点标记为「未入队」和「距离为正无穷」
Arrays.fill(vis, false);
Arrays.fill(dist, INF);
// 只有起点最短距离为 0
dist[k] = 0;
// 使用「双端队列」存储, 存储的是点编号
Deque<Integer> d = new ArrayDeque<>();
// 将「源点/起点」进行入队, 并标记「已入队」
d.addLast(k);
vis[k] = true;
while (! d.isEmpty()) {
// 每次从「双端队列」中取出, 并标记「未入队」
int poll = d.pollFirst();
vis[poll] = false;
// 尝试使用该点, 更新其他点的最短距离
// 如果更新的点, 本身「未入队」则加入队列中, 并标记「已入队」
for (int i = he[poll]; i != -1; i = ne[i])BFS 与 SPFA
BFS 中每个点只入列一次, 但有时, 我们可能需要 BFS 中允许一个点入列多次才能解决问题, 这种方法就是 SPFA.
SPFA 这种算法, 如果你百度的话, 你会发现大多是说他用于求最短路的, 事实上, 更宽泛的来理解, 所有可能要后悔的 BFS, 都可以用类似 SPFA 的思路来解决.
先说说经典的最短路问题, 希望大家能借此理解为何说 SPFA 是可以后悔的.
考虑这样一张图,$1$ 号点是起点, 边上的数字代表这条边的长度, 你想求出 $1$ 到 $10$ 号点的最短路.
下面, 说说为何朴素的 BFS 不行.
按照 BFS 的流程, 初始 $1$ 号点入列, 然后 $1$ 号点周围的 $2$ 号和 $3$ 号入列. 此时,$2$ 距 $1$ 最短路更新为 $4$, $3$ 距 $1$ 最短路更新为 $1$.
于是, 问题来了, 我们看到, 实际上 $1$ 到 $2$ 的最短路是 $1->3->4->2$, 其长度为 $3$.
但按照朴素的 BFS 来做, 由于已经有 vis[2]=1 了, 所以由 $4$ 号点访问周围点时,$2$ 号点就不会再入列了, 这样, 我们就会求出错误的最短路.
那怎么办呢? 一个很显然的办法, 那我就再把 $2$ 入列呗!
所以, SPFA 其实就是很简单的一件事儿:检测到某点距离变化, 就把某点入列.
并且如前所述, 这样的 SPFA 其实就不需要 vis 数组了, 因为只要距离更新, 点就要入列.
但下面代码中还是有 vis 数组, 其实他的含义是: 某个点当前正在队列里, vis 值为 1, 当前点不在队列里, vis 值为 0.
需要注意, 虽然名字都叫 vis, 但这里的 vis 数组和朴素 BFS 中的 vis 数组很不一样.
这里 vis 数组只是避免同一个点已经在队列里的情况下被加入队列多次而用的 (再次强调, SPFA 是允许一个点多次入列的, 只不过正在队列里的, 确实没必要再入列了).
那么具体看这道题,$dis[i][j]$ 表示到达第 $i$ 行第 $j$ 列的点所需要的最小花费, 直接的状态转移看上去并不好想.
怎么办?
不好想就不想了呗!
只要某个点 dis 变得更小了, 我们按照 SPFA 的思想, 就二话不说给他入列, 让他再更新周围点的 dis, 这样总是对的了吧.
所以说白了, SPFA, 听上去高大上, 其实是贼暴力的一种方法, 只要检测到某点 dis 值改变, 就在重新由这点开始 BFS, 仅此而已.
作者:fried-chicken
链接:https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/spfa-bfsde-yi-chong-kuo-zhan-by-fried-chicken/
来源: 力扣 (LeetCode)
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.
文章评论