SPFA 未死
拯救 SPFA 的优化策略
前言
:::warning[温馨提示]{open}
此篇文章并非 P4779 的题解，提及仅作为 SPFA 的效率参考。
评测性能可能有较小差异。
:::
OI 上有这样一句话:
"关于 SPFA, 它已经死了。"
但在一开始，我不这么认为。
下面是我两周的研究成果。
1 出路
准备
首先，从基础的 SPFA 开始。
struct edge { int u; long long w; };
vector<vector<edge> >gh; //邻接表
vector<long long>dis; //最短路
int s; //源点因为基础的 SPFA 会被卡(节点反复松弛)，会从平均的
SLF + LLL + swap
在网上已经有了很多基础的优化(SLF 和 LLL 等)。
:::info[SLF & LLL + swap]
SLF 优化(Small Label First)使用双端队列
deque来实现，基于一个贪心。在优化中，每次要往队列中加入新节点时，会将新节点与队头元素进行比较。如果新节点的距离小于队头元素的距离，则将新节点插入队头，否则插入队尾。这种方法可以减少不必要的松弛操作，让较优的路径先处理，从而提高算法的效率。LLL 优化(Large Label Last)调整队列中元素的出队顺序。在进行松弛操作时，如果队首元素的距离大于队列中所有距离的平均值，即
\sum\limits_{s \in Q}w_s < w_x \cdot \text{size}_Q 其中
x 为当前元素,Q 为队列，那么将队首元素移动到队尾，继续寻找下一个合适的元素进行松弛。
SLF 与 LLL 常常配合使用, SFL 可以
这里为了让队列更像优先队列(让队列中元素尽量总体上升)，辅助 SFL, 我们可以再加个 SLF-swap 来进一步提升性能。
这里分别编成了两个函数：
long long sumq; //当前队列中元素之和
//这里用双向队列deque支持SLF的放头操作
inline void push_node(deque<edge>& dq, edge v) { //SLF优化
if (gh[v.u].empty())return;
sumq += v.w;
if (dq.empty())dq.emplace_back(v);
else if (v.w >= dq.front().w)dq.emplace_back(v); //小->头,大->尾
else dq.emplace_front(v);
}
inline edge& get_node(deque<edge>& dq) { //LLL优化
static edge retg;
while ((retg = dq.front()).w * (int)dq.size() > sumq && dq.size() > 1) {
//意思是若当前元素比所有元素平均值小, 稍后处理
dq.emplace_back(dq.front());
dq.pop_front();
}
dq.pop_front();
if(dq.size() > 1){ //SFL-swap
edge x = dq.front(), y = dq.back();
if (dis[x.u] > dis[y.u]) {
dq.pop_front(), dq.pop_back();
dq.push_front(y), dq.push_back(x);
}
}
sumq -= retg.w;
return retg; //返回引用, 减小开销
}:::
阈值限制
到这并不够。
因为在 LLL 中我们有一层循环，当队列中前面元素都比平均值大时(SFL 并不保证队列严格单调不降)，这里可能最坏会劣化至
我测试的是
因为队列的元素数不会太多，且
这与根函数 (
(来自百度) :::info[阈值优化]
unsigned k = 0; //阈值
inline edge& get_node(deque<edge>& dq){
......
int _cnt = 0; //循环计数
while ((retg = dq.front()).w * (int)dq.size() > sumq && dq.size() > 1 && (_cnt++) < (dq.size() > k ? k : dq.size())) { //如果
dq.emplace_back(dq.front());
dq.pop_front();
}
dq.pop_front();
......
}
int main(){
......
scanf("%d %d %d", &n, &m, &s);
k = ((unsigned)sqrt(n) >> 1) + 1;
......
}::: 但这只是很一般的情况，特殊一点就不行了。
面对一些~毒瘤的~数据(网格图，链套菊花)，仍然会 TLE。
松弛优先级
我们可以知道, SPFA 被卡本质是因为在特定情况下，节点反复入队，而入队后还排上很长的队伍(之前的路径又会更新很多的次短路)，耗费太多时间。并且之前的点也会被卡，不断更新次短路，到当前节点了又是不断更新次短路，反反复复，浪费大量时间。
因此，我们让多次入队的节点(被卡的)排到队头，将通过这个节点的次短路一次处理干净，这样后面的路径要更新次短路时，就不满足松弛必要的三角形不等式条件了，一步到位，效率会高很多。
:::info[被卡节点优先]
vector<unsigned>cnt; //节点入队次数
//cnt[s] = 1;
inline void push_node(deque<edge>& dq, edge v) {
if (gh[v.u].empty())return;
sumq += v.w;
if (dq.empty())dq.emplace_back(v);
else if (v.w >= dq.front().w || cnt[v.u] > cnt[dq.front().u])dq.emplace_back(v); //与队头比较
else dq.emplace_front(v);
cnt[v.u]++; //统计入队次数
}::: 到这，已经可以在 P4779 单源最短路中过掉卡朴素 SPFA 的 5 个点。
但还有 1 个点，怎么过？
随机化选择
我们容易知道, SPFA 的时间复杂度依赖于路径的选择，前几个算法都是在尝试优化路径选择，但是有些阴险的出题人就会利用这种性质，专门出卡这种优化的数据(网格套菊花等)。
所以，根除被卡的方案，就是不按出题人想让你走的路线走(尽管“陷阱”可能是目前最优)。
为了让出题人抓不住我们的路径的把柄，我们使用随机数干扰决策！
尽管不稳定，且可能会牺牲小样例的时间，但至少很大几率不会掉进出题人的“陷阱”。
这好比你的程序在走迷宫，如果光用“左右手法制/墙随”(一直沿着一个方向的岔路走)等死板的方式来走，总有一些类型的迷宫走不出去或耗时很大(“回”字形等)。
但如果在岔路恰当改变决策，多试几次就能走出去。
SPFA 的随机决策优化也是如此。
应让随机数范围不要过大或过小(上限大概在
我使用的是 C++11 的<random>中的随机数类mt19937生成(当然也可以直接rand())
并且我们应该知道什么位置可以随机，什么位置不该随机。 :::info[完整代码] 可配合注释阅读
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<random>
using namespace std;
struct edge {
int u; long long w;
};
vector<vector<edge> >gh;
vector<long long>dis;
vector<unsigned>cnt;
long long sumq;
int s;
unsigned k = 0;
mt19937 ru; //随机数生成器
constexpr long long INF = (1ll << 31) - 1;
constexpr unsigned rantop = 6; //随机范围上限
#define getran() (ru() % rantop) //上限为rantop
inline void push_node(deque<edge>& dq, edge v) {
if (gh[v.u].empty())return;
sumq += v.w;
if (dq.empty())dq.emplace_back(v);
else if (cnt[v.u] > cnt[dq.front().u] && !getran())dq.emplace_front(v); //随机影响SFL决策
else if ((v.w >= dq.front().w) || !getran())dq.emplace_back(v); //24,25这两句的顺序并不是特别重要
else dq.emplace_front(v);
cnt[v.u]++;
}
inline edge& get_node(deque<edge>& dq) {
static edge retg; int _cnt = 0;
if (getran() || !getran()) { // 这里取适中的几率
while ((retg = dq.front()).w * (int)dq.size() > sumq && dq.size() > 1 && (_cnt++) < (dq.size() > k ? k : dq.size())) {
if ((_cnt & 1) && !getran())break; //循环内适当随机
dq.emplace_back(dq.front());
dq.pop_front();
}
dq.pop_front();
}
else { //取尾的几率不能太大，不然会产生大量的次短路松弛
while ((retg = dq.back()).w * (int)dq.size() > sumq && dq.size() > 1 && (_cnt++) < (dq.size() > k ? k : dq.size())) {
if ((_cnt & 1) && !getran())break;
dq.emplace_front(dq.back());
dq.pop_back();
}
dq.pop_back();
}
if (dq.size() > 1 && getran()) { //随机决定是否swap
edge x = dq.front(), y = dq.back();
if (dis[x.u] > dis[y.u]) {
dq.pop_front(), dq.pop_back();
dq.push_front(y), dq.push_back(x);
}
}
sumq -= retg.w;
return retg;
}
#define inque(x) (nstat[x] & 1) //节点x是否在队里
#define swapin(x) (nstat[x] ^= 1) //切换节点x的队列状态
void spfa() { //SPFA
for (int i = 1; i < dis.size(); i++)dis[i] = INF; //初始化
dis[s] = 0;
cnt[s] = 1;
deque<edge>dq; //队列
vector<unsigned char>nstat(gh.size()); //每个节点的状态
dq.push_back({ s, 0 }); //起点入队
swapin(s); //起点在队中
while (dq.size()) {
edge now = get_node(dq);
for (auto& sd : gh[now.u]) {
if (dis[sd.u] > sd.w + dis[now.u]) {//三角形不等式
dis[sd.u] = sd.w + dis[now.u];
if (!inque(sd.u))push_node(dq, { sd.u, dis[sd.u] }), swapin(sd.u); //添加节点，并标记为已入队
}
}
swapin(now.u); //标记为已出队
}
}
int main() {
ru.seed(time(0)); //种子
int n, m;
scanf("%d %d %d", &n, &m, &s);
k = ((int)sqrt(n) >> 1) + 1;
gh.resize(n + 1); //申请大小
dis.resize(n + 1);
cnt.resize(n + 1);
for (int i = 0; i < m; i++) {
int u;
edge tmps;
scanf("%d %d %lld", &u, &tmps.u, &tmps.w);
gh[u].emplace_back(tmps);
}
spfa();
for (int i = 1; i <= n; i++)printf("%lld ", dis[i]);
return 0;
}::: AC 记录 1， AC 记录 2， AC 记录 3。
时间复杂度平均应在
因为每次 LLL 不一定都要跑满
可以看到总时间均在 700ms 之内(差于 Dijkstra 的 400ms)，但因随机性不是非常稳定。(~hack 数据太强了~)
到这, SPFA 救活了吗？
对比
这是来自 yfzcsc 大佬的一段数据生产机代码(非负权，来自yfzcsc的博客)。
它可以生成极端数据。 :::info[极端数据生产机]
#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
using namespace std;
struct edge { int u, v, w; };
vector<edge>v;
int id[5000][5000], n, tp, m, a[1000000];
int r() {
return rand();
}
int main() {
freopen("in.txt", "w", stdout);
scanf("%d", &n);
m = 42866 / n;
srand(time(0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
id[i][j] = ++tp, a[tp] = tp;
int SIZE = 29989;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (i < n) {
v.push_back(edge{ id[i][j],id[i + 1][j],1 });
v.push_back(edge{ id[i + 1][j],id[i][j],1 });
if (j < m) {
if (1)v.push_back(edge{ id[i][j],id[i + 1][j + 1],r() % SIZE + 10 });
else v.push_back(edge{ id[i + 1][j + 1],id[i][j],r() % SIZE + 10 });
}
}
if (j < m) {
v.push_back(edge{ id[i][j],id[i][j + 1],r() % SIZE + 10 });
v.push_back(edge{ id[i][j + 1],id[i][j],r() % SIZE + 10 });
}
}
fprintf(stderr, "[%d,%d,%d]", (int)v.size(), n, m);
random_shuffle(v.begin(), v.end());
printf("%d %d %d\n", tp, (int)v.size(), 1);
for (int i = 0; i < v.size(); ++i)printf("%d %d %d\n", a[v[i].u], a[v[i].v], v[i].w);
}:::
| 这是我的优化 SPFA 与 Dijkstra 的对比( |
测试编号 | 基础 SLF+LLL 的 SPFA | 优化 SPFA | Dijkstra | |
|---|---|---|---|---|---|
:::info[测试代码] 随机上限做了微调。
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
#include<random>
using namespace std;
struct edge {
int u; long long w;
bool operator<(const edge& x)const noexcept {
return w > x.w;
}
};
vector<vector<edge> >gh;
vector<long long>dis;
vector<unsigned>cnt;
long long sumq;
int s;
unsigned k = 0;
mt19937 ru;
constexpr long long INF = (1ll << 31) - 1;
constexpr unsigned rantop = 7;
#define getran() (ru() % rantop)
inline void push_node(deque<edge>& dq, edge v) {
if (gh[v.u].empty())return;
sumq += v.w;
if (dq.empty())dq.emplace_back(v);
else if (cnt[v.u] > cnt[dq.front().u] && !getran())dq.emplace_front(v);
else if ((v.w >= dq.front().w) || !getran())dq.emplace_back(v);
else dq.emplace_front(v);
cnt[v.u]++;
}
inline edge& get_node(deque<edge>& dq) {
static edge retg; int _cnt = 0;
if (getran() || !getran()) {
while ((retg = dq.front()).w * (int)dq.size() > sumq && dq.size() > 1 && (_cnt++) < (dq.size() > k ? k : dq.size())) {
if ((_cnt & 1) && !getran())break;
dq.emplace_back(dq.front());
dq.pop_front();
}
dq.pop_front();
}
else {
while ((retg = dq.back()).w * (int)dq.size() > sumq && dq.size() > 1 && (_cnt++) < (dq.size() > k ? k : dq.size())) {
if ((_cnt & 1) && !getran())break;
dq.emplace_front(dq.back());
dq.pop_back();
}
dq.pop_back();
}
if (dq.size() > 1 && getran()) {
edge x = dq.front(), y = dq.back();
if (dis[x.u] > dis[y.u]) {
dq.pop_front(), dq.pop_back();
dq.push_front(y), dq.push_back(x);
}
}
sumq -= retg.w;
return retg;
}
#define inque(x) (nstat[x] & 1)
#define swapin(x) (nstat[x] ^= 1)
void spfa() { //SPFA
dis[s] = 0;
cnt[s] = 1;
deque<edge>dq; //队列
vector<unsigned char>nstat(gh.size());
dq.push_back({ s, 0 });
swapin(s);
while (dq.size()) {
edge now = get_node(dq);
for (auto& sd : gh[now.u]) {
if (dis[sd.u] > sd.w + dis[now.u]) {
dis[sd.u] = sd.w + dis[now.u];
if (!inque(sd.u))push_node(dq, { sd.u, dis[sd.u] }), swapin(sd.u);
}
}
swapin(now.u);
}
}
namespace _simple { //SFL+LLL的普通SPFA
inline void push_node(deque<edge>& dq, edge v) {
if (gh[v.u].empty())return;
sumq += v.w;
if (dq.empty())dq.emplace_back(v);
else if ((v.w >= dq.front().w))dq.emplace_back(v);
else dq.emplace_front(v);
}
inline edge& get_node(deque<edge>& dq) {
static edge retg; int cnt = 0;
while ((retg = dq.front()).w * (int)dq.size() > sumq && dq.size() > 1) {
dq.emplace_back(dq.front());
dq.pop_front();
}
dq.pop_front();
sumq -= retg.w;
return retg;
}
void spfa() { //SPFA
dis[s] = 0;
deque<edge>dq;
vector<unsigned char>nstat(gh.size());
dq.push_back({ s, 0 });
swapin(s);
while (dq.size()) {
edge now = _simple::get_node(dq);
for (auto& sd : gh[now.u]) {
if (dis[sd.u] > sd.w + dis[now.u]) {
dis[sd.u] = sd.w + dis[now.u];
if (!inque(sd.u))_simple::push_node(dq, { sd.u, dis[sd.u] }), swapin(sd.u);
}
}
swapin(now.u);
}
}
}
void dijkstra() {
priority_queue<edge, vector<edge> >pq;
pq.push({ s, 0 });
dis[s] = 0;
vector<bool>vis(dis.size());
while (!pq.empty()) {
edge now = pq.top();
pq.pop();
if (vis[now.u])continue;
vis[now.u] = 1;
for (auto& sd : gh[now.u]) {
if (dis[sd.u] > now.w + sd.w) {
dis[sd.u] = now.w + sd.w;
if (!vis[sd.u])pq.push({ sd.u, dis[sd.u] });
}
}
}
}
int main() {
freopen("in.txt", "r", stdin);
ru.seed(time(0));
int n, m;
scanf("%d %d %d", &n, &m, &s);
k = ((int)sqrt(n) >> 1) + 1;
gh.resize(n + 1);
dis.resize(n + 1);
cnt.resize(n + 1);
for (int i = 0; i < m; i++) {
int u;
edge tmps;
scanf("%d %d %lld", &u, &tmps.u, &tmps.w);
gh[u].emplace_back(tmps);
}
//测试
for (int i = 1; i < dis.size(); i++)dis[i] = INF;
puts("start spfa!");
clock_t st = clock();
spfa();
clock_t ed = clock();
double cpu_time_used = static_cast<double>(ed - st) / CLOCKS_PER_SEC;
printf("spfa used: %lld ms\n", (long long)(cpu_time_used * 1000));
for (int i = 1; i < dis.size(); i++)dis[i] = INF;
puts("start dijstra!");
st = clock();
dijkstra();
ed = clock();
cpu_time_used = static_cast<double>(ed - st) / CLOCKS_PER_SEC;
printf("dijkstra used: %lld ms\n", (long long)(cpu_time_used * 1000));
for (int i = 1; i < dis.size(); i++)dis[i] = INF;
puts("start basic SPFA!");
st = clock();
_simple::spfa();
ed = clock();
cpu_time_used = static_cast<double>(ed - st) / CLOCKS_PER_SEC;
printf("basic SPFA used: %lld ms\n", (long long)(cpu_time_used * 1000));
return 0;
}::: 似乎 SPFA 可以追上 Dijkstra !!!
但随机数毕竟是不稳定的，要是你的运气极其的差, 效率可能不如普通 SPFA ......
所以, SPFA 半死不活了。
2 后记
缘由与建议
既然 Dijkstra 已经那么好用了，为什么还要尝试优化“已死”的 SPFA 呢？
我认为有两点：
- SPFA 可以处理负权边，判断负环，这是绝对的优势；
- 网上很多人不断尝试优化，但绝大部分都被 Hack 数据干掉了。
- 最重要的，我想要知道 SPFA 已经死了，这个说法是否正确。
并且未来肯定有更多的优化方案，我的这些不过是冰山一角。
但还是在非负权时建议使用 Dijkstra, 原因：
- Dijkstra 时间稳定在
O(E \log V) , 比优化 SPFA 的O(KE \cdot \sqrt{V}) 明显更快更稳。 - 优化的 SPFA 码量巨大，码量约为 Dijkstra 的 3 倍，是线段树的规模。
- 阴险的出题人会不断产生新的 Hack 数据，没准就失效了。
应该存在 Hack 数据可以将我的优化代码卡到 TLE 的(试了一大堆，都没有)，如果发现了请指出。
如果这篇片面的文章给了你一些启发，或者帮助到了你，请留下个赞。
但本蒟蒻才刚入谷不到 4 个月，欢迎各位大佬在评论区批评并指正错误。
也感谢洛谷提供的好平台，让我能分享我的经验。
谢谢大家的支持！！