SPFA优化算法-SLF_Swap

SPFA他死了

出于众所周知的原因，SPFA他死了。但是我们可以通过一些简单的优化来挽回一点点（对于存心针对优化卡SPFA的数据依然没有办法）。

首先 SPFA 的最坏时间复杂度是 $O(n^2)$ 的，对于堆优化 Dijkstra 的 $O(n\log n)$ 是被完爆的。而优化实际上是让队列接近于优先队列的 $\log n$ 级别。

1. SLF(Small Label First) 优化 使用双端队列，每当插入元素时，与队首距离进行比较，若插入元素距离小于队首距离则从队首插入，否则从队尾插入。
2. LLL(Large Label Last) 优化 同样使用双端队列，维护目前队列中元素到起点的距离的平均值，若大于平均值则从队尾插入，否则从队首插入。

但是上面两种是很容易被卡的，因此容错SLF和MCFX就出现了。

1. 容错SLF 定义容错值，当插入元素距离减去容错值小于队首距离时从队尾插入，否则从队首插入。
2. MCFX优化 定义一个区间，当入队节点的入队次数属于这个区间的时候，从队首插入，否则从队尾插入。

随后总算来到了今天的重头戏 SLF_Swap 。

SLF_Swap 在队列改变时判断如果队首距离大于队尾距离则交换首尾元素。

代码示例如下：

void SLF_Swap() {
    if (!q.empty() && dis[q.front()] > dis[q.back()]) {
        int x = q.front();
        int y = q.back();
        q.pop_front();
        q.pop_back();
        q.push_front(y);
        q.push_back(x);
        return;
    }
}

当然还有一些随机化的优化，比如打乱边序，随机首尾入队，随机打乱队列之类，但是这些都比较玄学，能不能过纯看运气。

---

写在最后

这是本站的第一篇博客，感觉要庆祝一下。

但是不知道写什么就把自己几年前初学时候写的放上来。