关于 SPFA，它死了。
以前的最短路算法一直都用的 SPFA，说到原因，那就是兼容性和速度都比较好 （而且好写），毕竟 Dijkstra 不能处理存在负环的情况。
然而 NOI2018 出现了卡 SPFA 的构造数据，于是洛谷是出现了加强后的单源最短路径的模板题。
当然我这个蒟蒻为什么要去管 NOI 呢
SPFA 算法
基本思路
基本思路是维护一个队列，取出队首，遍历从队首出发的所有有向边，然后执行松弛操作，并把没有入过队的点放入队列中，类似于 BFS，直到队列为空。
当然要注意的是要先把源点赋值为 0，给未知的点赋上一个极大值，如 0x7fffffff（7 个 f，十进制是 2147483647）。
分步模拟
这是洛谷最短路模板样例的图，其中黄色的是源点。
先这样进行初始化
然后开始进行 SPFA，枚举从源点出发的边（），并把 加入到队列中。
因为满足松弛条件 dis[v] > dis[1] + cost，所以执行松弛操作。当前最短路径用蓝色标注。
继续取出队首 2，枚举从队首 2 出发的边（），因为 已在队列中（用一个 bool 数组标记是否入队），所以不用再重复进队。
都满足松弛条件 dis[v] > dis[2] + cost，继续进行松弛。当前最短路径还是用蓝色标注。
取出队首 3，枚举出边，不满足松弛条件，故不进行操作。
取出队首 4，然而 4 没有出边，不进行任何操作。
此时队列为空，跳出循环，dis 数组的值即为所求数值。
代码
#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 自然要在堆顶。
再取出堆顶元素 2，继续枚举出边，发现依然满足松弛条件，继续松弛操作并把这些边所连点放入堆中。
取出堆顶元素 4，该点没有出边，所有不进行操作，继续下一步。
由于堆顶元素满足优化条件 top.second = 4 > dis[4] = 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 复杂度为 ，其中 是一个常数， 为边数，极端复杂度为 ，其中 为点数，极端构造数据可以卡成这个复杂度，所以推荐在没有负边的情况下使用 Dijkstra。 Dijkstra 加入堆优化后复杂度为 ，可以说是很快的算法了。