关于 SPFA,它死了。

以前的最短路算法一直都用的 SPFA,说到原因,那就是兼容性和速度都比较好(而且好写),毕竟 Dijkstra 不能处理存在负环的情况。

然而 NOI2018 出现了卡 SPFA 的构造数据,于是洛谷是出现了加强后的单源最短路径的模板题


当然我这个蒟蒻为什么要去管 NOI 呢

SPFA 算法

基本思路

基本思路是维护一个队列,取出队首,遍历从队首出发的所有有向边,然后执行松弛操作,并把没有入过队的点放入队列中,类似于 BFS,直到队列为空。
当然要注意的是要先把源点赋值为 0,给未知的点赋上一个极大值,如 0x7fffffff(7 个 f,十进制是 2147483647)。

分步模拟

这是洛谷最短路模板样例的图,其中黄色的是源点。

先这样进行初始化

0
0

然后开始进行 SPFA,枚举从源点出发的边($1\to 2,1\to 3,1\to 4$),并把 $2,3,4$ 加入到队列中。
因为满足松弛条件 dis[v] > dis[1] + cost,所以执行松弛操作。当前最短路径用蓝色标注。

1
1

继续取出队首 2,枚举从队首 2 出发的边($2\to 3,2\to 4$),因为 $3,4$ 已在队列中(用一个 bool 数组标记是否入队),所以不用再重复进队。
都满足松弛条件 dis[v] > dis[2] + cost,继续进行松弛。当前最短路径还是用蓝色标注。

2
2

取出队首 3,枚举出边,不满足松弛条件,故不进行操作。

3
3

取出队首 4,然而 4 没有出边,不进行任何操作。
此时队列为空,跳出循环,dis 数组的值即为所求数值。

4
4

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
const int maxM = 5e5 + 5, maxN = 1e4 + 5;
struct Edge {
    int next, to, cost;
} edge[maxM];
int dis[maxN], head[maxM];
int n, m, s, cnt = 0;
bool used[maxN];
template<typename Tp> void read(Tp &x) {
    char c = getchar(); int f = 1; x = 0;
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    do {
        x = x * 10 + (c ^ 48);
        c = getchar();
    } while (isdigit(c));
    x *= f;
}
void add(int from, int to, int cost) {
    edge[++cnt].next = head[from];
    edge[cnt].to = to;
    edge[cnt].cost = cost;
    head[from] = cnt;
}
void spfa() {
    queue<int> que;
    fill(dis, dis + n + 1, INF);
    que.push(s);
    dis[s] = 0;
    used[s] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        used[u] = false;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                if (!used[v]) {
                    used[v] = true;
                    que.push(v);
                }
            }
        }
    }
}
int main() {
    read(n), read(m), read(s);
    for (int i = 1; i <= m; i++) {
        int from, to, cost;
        read(from), read(to), read(cost);
        add(from, to, cost);
    }
    spfa();
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
}

Dijkstra 算法

基本思路

使用了贪心策略,从源点出发,贪心地选择距离源点最近的点作为下一个点,并枚举所有出边进行松弛操作的。
初始化也和 SPFA 一样,只是我们可以采用堆这种数据结构来进行贪心地选取,这样可以有效降低复杂度。

其中堆存放的是包含两个数的二元组,一个存放的是编号,另一个存放的是当前到源点的最短距离。
这个小根堆就是根据第二个值来存取数据的。
可以使用 STL 自带的 priority_queue(优先队列)来实现(不要忘记 priority 的拼法,尤其对于没有自动补全的编辑器来说

小小的优化

在进行贪心时,要把所有明显不符合条件的情况跳过,类似于剪枝。
当二元组存储的距离与 dis 数组不同时(更大时)直接弹出并跳过,出现这种情况是因为堆有重复存储的点。
即当 top.second > dis[top] 时跳过。

分步模拟

还是用上面那个图,初始化如下

从 1 开始,所有边都满足松弛条件,进行松弛。将这些边所连点放入小根堆中,距离源点最近的点 2 自然要在堆顶。

1
1

再取出堆顶元素 2,继续枚举出边,发现依然满足松弛条件,继续松弛操作并把这些边所连点放入堆中。

2
2

取出堆顶元素 4,该点没有出边,所有不进行操作,继续下一步。

4
4

由于堆顶元素满足优化条件 top.second = 4 > dis[4] = 3,故弹出并跳过。
继续取出堆顶元素 3,没有可以执行松弛操作的点,继续下一步。

3
3

由于堆顶元素满足依然优化条件 top.second = 5 > dis[3] = 4,故弹出并跳过。
最后堆为空,结束循环,此时 dis 数组储存的即为结果。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e5 + 3;
const int INF = 0x7fffffff;
struct Edge {
    int next, to, cost;
} edge[maxN];
struct node {
    int first, second;
    bool operator <(const node& rhs) const {
        return second > rhs.second;
    }
};
int n, m, s;
int head[maxN], dis[maxN];
int cnt = 0;
template<typename Tp> void read(Tp &x) {
    char c = getchar();
    x = 0;
    while (!isdigit(c)) c = getchar();
    do {
        x = x * 10 + (c ^ 48);
        c = getchar();
    } while (isdigit(c));
}
void add(int from, int to, int cost) {
    edge[++cnt].next = head[from];
    edge[cnt].to = to;
    edge[cnt].cost = cost;
    head[from] = cnt;
}
void dijkstra() {
    priority_queue<node> hep;
    fill(dis, dis + n + 1, INF);
    dis[s] = 0;
    hep.push((node) {s, 0});
    while (!hep.empty()) {
        node frt = hep.top();
        hep.pop();
        int u = frt.first;
        if (frt.second > dis[u]) continue;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                hep.push((node) {v, dis[v]});
            }
        }
    }
}
int main() {
    read(n), read(m), read(s);
    for (int i = 1; i <= m; i++) {
        int from, to, cost;
        read(from), read(to), read(cost);
        add(from, to, cost);
    }
    dijkstra();
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
}

总结

两种算法都是单源最短路的算法,其中 SPFA 复杂度为 $O(KM)$,其中 $K$ 是一个常数,$M$ 为边数,极端复杂度为 $O(NM)$,其中 $N$ 为点数,极端构造数据可以卡成这个复杂度,所以推荐在没有负边的情况下使用 Dijkstra。
Dijkstra 加入堆优化后复杂度为 $O(M\log N)$,可以说是很快的算法了。