最短路算法2——SPFA

概述

最短路算法1——Dijkstra中,我介绍了 Dijkstra 算法,其中给出了一种奇怪的优先队列优化,优化后的代码其实有点不像 Dijkstra 算法,而更像今天要介绍的 SPFA(Shortest Path Faster Algorithm) 算法。SPFA 算法也是一种单源最短路算法,实际上是 Bellman-Ford 算法的队列优化,它最大的特点是它可处理有负权边的图,并可以判断是否存在负值圈。

思想

SPFA 算法采用动态逼进法,使用队列保存待优化的顶点,从队列中取出一点对其邻接点进行优化,若有调整则将其入队等待调整。反复取出队首更新最短路,直至队列为空。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int MAX_N = 100;

struct edge { int next, weight;};
vector<edge>G[MAX_N];

bool inq[MAX_N];
int dist[MAX_N];

void spfa(int s) {
memset(inq, false, sizeof(inq));
memset(dist, 0x3f, sizeof(dist));

dist[s] = 0;
inq[s] = true;

queue<int> que;
que.push(s);

while (!que.empty()) {
int u = que.front();
que.pop();
inq[u] = false;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].next;
if (dist[u] + G[u][i].weight < dist[v]) {
dist[v] = dist[u] + G[u][i].weight;
if (!inq[v]) {
que.push(v);
inq[v] = true;
}
}
}
}
}
  • G 邻接表
  • inq 标示顶点是否已入队
  • dist 保存起始点到各个点的距离
  • que 保存等待优化的顶点

应用

负值圈判断

在 SPFA 算法中增加 cnt 数组记录顶点入队次数,如果入队次数大于顶点总数 n 说明存在负值圈。

补充后部分代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
queue<int> que;
que.push(s);
cnt[s]++; // **
while (!que.empty()) {
int u = que.front();
que.pop();
inq[u] = false;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].next;
if (dist[u] + G[u][i].weight < dist[v]) {
dist[v] = dist[u] + G[u][i].weight;
if (!inq[v]) {
que.push(v);
cnt[v]++; // **
inq[v] = true;
if(cnt[v] > n){ // **
cout << "存在负值圈" << endl;
return;
}
}
}
}
}

最长路

方法 1

将边权取相反数,跑完算法后,dist 数组的值为距离的相反数。

方法 2

  • 将更新操作改为的条件 dist[u] + G[u][i].weight > dist[v]
  • 初始化 dist 数组时给予极小值如 0xbf
1
2
3
4
memset(dist, 0xbf, sizeof(dist));
...
if (dist[u] + G[u][i].weight > dist[v])
...

差分约束系统

如果一个不等式组由 $n​$ 个变量和 $m​$ 个约束条件组成,且每个约束条件都是形如 $x_j - x_i \leq k, 1 \leq i,j \leq n​$ 的不等式,则称其为差分约束系统。

$x_j - x_i \leq k$ 对应于最短路网络中的三角不等式 $dist_v - dist_u \leq w_{<u,v>}$,即 $dist_v + w_{<u,v>} \leq dist_u$。用最短路算法得到答案 $dist_i$,也就求出了不等式组的一个解。

增加一个超级源 $s$ ,$s$ 连接其余每个顶点,边权均为 $0$。执行 SPFA 算法,如果未出现负值圈 dist 数组即满足条件的一组解,反之不等式组无解。

由于差分约束系统可能出现负权边和负值圈,所以基本只能用 SPFA 算法解决。

$x_j - x_i \leq k​$

  • 求最短路变形为 $x_i +k \geq x_j​$ 从 $i​$ 到 $j​$ 连一条权值为 $k​$ 的边
  • 求最短路变形为 $x_j - k \leq x_i$ 从 $j$ 到 $i$ 连一条权值为 $-k$ 的边

优化

SPFA 算法有两种优化方式

  • SLF:Small Label First 策略
  • LLL:Large Label Last 策略

SLF 可使速度提升 $15\sim20\%$;SLF + LLL 可提高约 $50\%$

SLF

设要入队的顶点为 $j$ ,队首元素为 $i$ ,若 $dist[j] < dist[i]$ ,则将 $j$ 从队首入队,反之从队尾入队。

实现上需要在队首插入元素,需要将容器从 queue 改为 deque 双端队列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void spfa(int s) {
memset(inq, false, sizeof(inq));
memset(dist, 0x3f, sizeof(dist));

dist[s] = 0;
inq[s] = true;

deque<int> que;
que.push_back(s);
while (!que.empty()) {
int u = que.front();
que.pop_front();
inq[u] = false;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].next;
if (dist[u] + G[u][i].weight > dist[v]) {
dist[v] = dist[u] + G[u][i].weight;
if (!inq[v]) {
if(dist[i] < dist[que.front()]){
que.push_front(v);
}else{
que.push_back(v);
}
inq[v] = true;
}
}
}
}
}

LLL

设队首元素为 $i$ ,队列中所有最短距离值的平均值为 $x$ ,若 $d[i] > x$ 则将其插入到队尾,查找下一个元素,直到找到某一顶点 $i$ 使得 $d[i] < x$ ,则将 $i$ 出队进行松弛操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void spfa(int s) {
memset(inq, false, sizeof(inq));
memset(dist, 0x3f, sizeof(dist));
int sum = 0,cnt = 1; // **
dist[s] = 0;
inq[s] = true;

deque<int> que;
que.push_back(s);
while (!que.empty()) {
int u = que.front();
que.pop_front();
inq[u] = false;
if(dist[u] * cnt > sum){
que.push_back(u);
continue;
}
sum -= dist[u]; // **
cnt--;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].next;
if (dist[u] + G[u][i].weight > dist[v]) {
dist[v] = dist[u] + G[u][i].weight;
if (!inq[v]) {
que.push_back(v);

inq[v] = true;
sum += dist[v]; // **
cnt++;
}
}
}
}
}

SLF + LLL

综合 SLF 策略和 LLL 策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void spfa(int s) {
memset(inq, false, sizeof(inq));
memset(dist, 0x3f, sizeof(dist));
int sum = 0,cnt = 1;
dist[s] = 0;
inq[s] = true;

deque<int> que;
que.push_back(s);
while (!que.empty()) {
int u = que.front();
que.pop_front();
inq[u] = false;
if(dist[u] * cnt > sum){ // LLL
que.push_back(u);
continue;
}
sum -= dist[u];
cnt--;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].next;
if (dist[u] + G[u][i].weight > dist[v]) {
dist[v] = dist[u] + G[u][i].weight;
if (!inq[v]) {
// SLF
if(dist[i] < dist[que.front()]){
que.push_front(v);
}else{
que.push_back(v);
}
inq[v] = true;
sum += dist[v];
cnt++;
}
}
}
}
}

复杂度分析

设 $V$ 代表结点的个数,$E$ 代表边的个数。

空间复杂度

除去邻接表的空间占用,SPFA 算法额外空间开销显然为 $O(V)$

时间复杂度

如果顶点的平均入队次数为 $k$ ,则 SPFA 算法的时间复杂度为 $O(kE)$,对于较为随机的稀疏图,根据经验 $k$ 一般不超过 $4$ 。

SPFA 的本质是 Bellman-Ford 算法的队列优化,本质上没有改变 Bellman-Ford 算法的时间复杂度,对于稠密图来说,SPFA 最坏仍是 $O(VE)$ 的时间复杂度,远差于 Dijkstra 算法的 $O( (V + E) \log V )$ 复杂度。

本文标题:最短路算法2——SPFA

文章作者:pazyx.xyz

发布时间:2019年02月02日 - 08:02

最后更新:2019年02月02日 - 17:02

原始链接:https://blog.pazyx.xyz/2019/02/02/spfa/

许可协议: 署名-非商业性使用-相同方式分享 4.0 国际 转载请保留原文链接及作者。

Donate comment here