队列优化后的Bellman-Ford算法
SPFA最短路径快速算法，Shortest Path Faster Algorithm
n n n 代表图的顶点数量， m m m 代表图的边的数量
平均时间复杂度 O ( m ) Omicron(m) O(m)
最坏时间复杂度 O ( n m ) Omicron(nm) O(nm)
对BF进行优化关于SPFA的最坏时间复杂度，参考
- Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
- 如何看待 SPFA 算法已死这种说法？
观察Bellman Ford算法流程
算法主要是两重循环
每一次迭代，都是遍历所有的边，进行松弛操作
只有当一个边的起点 a a a 更新过时，终点 b b b 的 d i s t dist dist 才可能会变小
基于此，可以用队列进行优化，类似BFS的代码形式
每一次，对所有以队首元素为起点的边的终点执行松弛操作，只将更新过的终点加入队列中，直至队列为空
算法流程伪代码
// 赋初值
for each vertex v in V
dist[v] = INF
dist[orig] = 0
Q.offer(orig)
while Q is not empty
u = Q.poll()
for each edge (a, b) in E(G)
if dist[a] + w(a, b) < dist[b] // 松弛操作
dist[b] = dist[a] + w(a, b)
if b is not in Q
Q.offer(b)
Tips
1.
SPFA算法无需备份dist数组，因为SPFA求解最短路时，不考虑边数限制
2.队列里都是由起点更新到的顶点，不存在bellman-ford算法中未更新的点同样被边更新的情况
代码实现核心代码
st数组的含义，true:代表队列中存在该顶点，可以避免重复更新
int[] spfa() {
Arrays.fill(dist, INF);
dist[1] = 0;
Queue q = new LinkedList<>();
q.offer(1);
st[1] = true;
while (!q.isEmpty()) {
int cur = q.poll();
st[cur] = false; // st数组，true:代表队列中有该顶点
for (int i = h[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[cur] + w[i]) {
dist[j] = dist[cur] + w[i];
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
return dist;
}
{% note java完整代码 %}
acwing 51. spfa求最短路
import java.util.*;
import java.io.*;
class Main{
static final int N = 100010;
static final int M = 100010;
static final int INF = 0x3f3f3f3f;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[M];
static int idx;
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int n, m;
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
public static void main(String[] args) throws Exception {
String[] str = cin.readLine().split(" ");
n = Integer.parseInt(str[0]); m = Integer.parseInt(str[1]);
int a, b, c;
Arrays.fill(h, -1);
for (int i = 0; i < m; ++i) {
str = cin.readLine().split(" ");
a = Integer.parseInt(str[0]); b = Integer.parseInt(str[1]); c = Integer.parseInt(str[2]);
add(a, b, c);
}
spfa();
cin.close();
}
static void spfa() {
Arrays.fill(dist, INF);
dist[1] = 0;
Queue q = new LinkedList<>();
q.offer(1);
st[1] = true;
while (!q.isEmpty()) {
int cur = q.poll();
st[cur] = false;
for (int i = h[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[cur] + w[i]) {
dist[j] = dist[cur] + w[i];
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
if (dist[n] == INF) System.out.println("impossible");
else System.out.println(dist[n]);
}
}
{% endnote %}
优化技巧可以通过优化队列质量来提升整体性能
@Wiki
距离小者优先(Small Label First, SLF)，由Bertsekas在Networks, 第23期, 1993, P703-P709中最先提出
松弛操作时，将更新的顶点和队列首部元素比较，如果 dist[b] < dist[q.peekFirst] text{dist[b] < dist[q.peekFirst]} dist[b] < dist[q.peekFirst] ，则将顶点 b b b 放入队首 q.offerFirst(b) text{q.offerFirst(b)} q.offerFirst(b)
spfa判断负环应用SPFA算法判断图中是否存在负权回路
原理同Bellman Ford算法，都是利用「抽屉原理」判断负环
假如图有 n n n 个顶点，若存在一个最短路径长度为 n n n 的话，此路径上有 n + 1 n + 1 n+1 个点，一定有两个点是同一个顶点，即存在环路
实现逻辑引入一个新数组 c o u n t [ ] count[] count[] 来记录路径的长度（边数）
发生更新
d
i
s
t
[
b
]
=
d
i
s
t
[
a
]
+
w
e
i
g
h
t
<
a
→
b
>
dist[b] = dist[a] + weight
dist[b]=dist[a]+weight
c o u n t [ b ] = c o u n t [ a ] + 1 count[b] = count[a] + 1 count[b]=count[a]+1
一旦 c o u n t [ b ] ≥ n count[b] ge n count[b]≥n ，证明存在环路
代码核心代码
注意，负权回路不一定是从源点出发的
因此一开始，将所有点放入队列中
boolean spfa() {
Arrays.fill(dist, INF);
dist[1] = 0;
Queue q = new LinkedList<>();
// 将所有点放入队列
for (int i = 1; i <= n; ++i) {
st[i] = true;
q.offer(i);
}
while (!q.isEmpty()) {
int cur = q.poll();
st[cur] = false; // st数组，true:代表队列中有该顶点
for (int i = h[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[cur] + w[i]) {
dist[j] = dist[cur] + w[i];
cnt[j] = cnt[cur] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
return false;
}
{% note java完整代码 %}
acwing 852. spfa判断负环
给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
请判断图中是否存在负权回路。
import java.util.*;
import java.io.*;
class Main {
static final int N = 2010;
static final int M = 10010;
static final int INF = 0x3f3f3f3f;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[M];
static int idx;
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int[] cnt = new int[N];
static int n, m;
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
public static void main(String[] args) throws Exception {
String[] str = cin.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
int a, b, c;
Arrays.fill(h, -1);
for (int i = 0; i < m; ++i) {
str = cin.readLine().split(" ");
a = Integer.parseInt(str[0]);
b = Integer.parseInt(str[1]);
c = Integer.parseInt(str[2]);
add(a, b, c);
}
boolean res = spfa();
if (res) System.out.println("Yes");
else System.out.println("No");
cin.close();
}
static boolean spfa() {
Arrays.fill(dist, INF);
dist[1] = 0;
Queue q = new LinkedList<>();
//
for (int i = 1; i <= n; ++i) {
st[i] = true;
q.offer(i);
}
while (!q.isEmpty()) {
int cur = q.poll();
st[cur] = false; // st数组，true:代表队列中有该顶点
for (int i = h[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[cur] + w[i]) {
dist[j] = dist[cur] + w[i];
cnt[j] = cnt[cur] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
return false;
}
}
{% endnote %}
参考资料- 最短路径快速算法–Wiki
- Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
- 如何看待 SPFA 算法已死这种说法？
原文发布于 图论：单源最短路径问题-SPFA | 向阳花
欢迎关注个人博客 https://floatu.top
