浅谈SPFA算法的优化

· · 个人记录

SPFA算法最坏情况的的时间复杂度是 O(VE)，很容易被卡。但SPFA算法有三种优化方式：SLF、LLL、SLF+LLL、Dfs。

1.SLF（Small Lable First）

顾名思义，就是把较小元素提前。

每次求最短路时，我们肯定希望用距离最短的点松弛。那如果一上来就找到这个点岂不是爽歪歪？SLF优化的思想就是如果新入队的元素比对手元素还要小，就加入到队首，否则加入到队尾（需要用双端队列）。

Code:

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int p,w;
};
int n,m;
int dis[2001];
bool vis[2001];
vector<Edge> e[2001];
deque<int> q;
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    q.push_back(1);
    dis[1]=0;
    while (q.size()){
        int now=q.front();
        q.pop_front();
        vis[now]=0;
        for (int i=0;i<e[now].size();i++){
            int p=e[now][i].p;
            int w=e[now][i].w;
            if (dis[p]>dis[now]+w){
                dis[p]=dis[now]+w;
                if (!vis[p]){
                    if (dis[p]<=dis[now]){
                        q.push_front(p);
                    }else{
                        q.push_back(p);
                    }
                    vis[p]=1;
                }
            }
        }
    }
    cout<<dis[n];
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    spfa();
    return 0;
}

2.LLL（Large Lable First）

顾名思义，就是大的放后面。

你可能会说，这不是跟SLF一样吗？

不，它针对的是出队元素。它的实现过程是：对于每个出队元素，比较它的距离和队列中距离的平均值，如果它的距离更大，将它弹出放到队尾。以此类推，直至有一个元素的距离小于其平均值。

Code:

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int p,w;
};
int n,m,sum,cnt=1;
int dis[2001];
bool vis[2001];
vector<Edge> e[2001];
queue<int> q;
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    q.push(1);
    dis[1]=0;
    cnt=1;
    while (q.size()){
        int now=q.front();
        while (dis[now]*cnt>sum){
            q.pop();
            q.push(now);
            now=q.front();
        }
        q.pop();
        cnt--;
        sum-=dis[now];
        vis[now]=0;
        for (int i=0;i<e[now].size();i++){
            int p=e[now][i].p;
            int w=e[now][i].w;
            if (dis[p]>dis[now]+w){
                dis[p]=dis[now]+w;
                if (!vis[p]){
                    q.push(p);
                    sum+=dis[p];
                    cnt++;
                    vis[p]=1;
                }
            }
        }
    }
    cout<<dis[n];
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    spfa();
    return 0;
}

3.SLF+LLL

一个针对入队元素，一个针对出队元素，两者互不影响，不就可以合起来了吗？

Code:

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int p,w;
};
int n,m,sum,cnt=1;
int dis[2001];
bool vis[2001];
vector<Edge> e[2001];
deque<int> q;
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    q.push_back(1);
    dis[1]=0;
    cnt=1;
    while (q.size()){
        int now=q.front();
        while (dis[now]*cnt>sum){
            q.pop_front();
            q.push_back(now);
            now=q.front();
        }
        q.pop_front();
        cnt--;
        sum-=dis[now];
        vis[now]=0;
        for (int i=0;i<e[now].size();i++){
            int p=e[now][i].p;
            int w=e[now][i].w;
            if (dis[p]>dis[now]+w){
                dis[p]=dis[now]+w;
                if (!vis[p]){
                    if (dis[p]<=dis[now]){
                        q.push_front(p);
                    }else{
                        q.push_back(p);
                    }
                    sum+=dis[p];
                    cnt++;
                    vis[p]=1;
                }
            }
        }
    }
    cout<<dis[n];
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    spfa();
    return 0;
}

4.Dfs

我们目前的算法和Bfs比较接近，但每次都会把元素放到队尾，造成了迭代的中断。那可不可以替换成搜索的另一利器——Dfs呢？这样就可以一下更新到底，每次更新都与上一次更新连续，不会造成迭代中断。

Code:

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int p,w;
};
int n,m,sum,cnt=1;
int dis[2001];
bool vis[2001];
vector<Edge> e[2001];
deque<int> q;
void spfa(int u){
    vis[u]=1;
    for (int i=0;i<e[u].size();i++){
        int p=e[u][i].p;
        int w=e[u][i].w;
        if (dis[p]>dis[u]+w){
            if (vis[p]){//如果一条路径上出现两个相同的点，则说明出现负环
                cout<<"负环";
                exit(0);
            }
            dis[p]=dis[u]+w;
            spfa(p);
        }
    }
    vis[u]=0;
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    spfa(1);
    cout<<dis[n];
    return 0;
}

该优化主要运用于判负环，时间复杂度可达 O(E)。虽然同样适用于构造网格图，但如果真要求最短路还是打前三个优化吧……

番外

虽然SPFA算法有四种优化，但我们要铭记一点：

没错，就算SFPA算法有四种优化，但死了终究是死了给一个死人化妆有个屁用啊，所以情况允许一定首选Dijkstra！！！

继上回

SPFA：“不！我不想S！！”

“你已经S了，S的透透的”