最短路四连：致逝去的SPFA

前言

如题，这里讲解四个最短路，Floyd，dijkstra+堆优化，Bellman-ford，SPFA。(后面两个不是一样的嘛...)

 进入正题吧。

Floyd：求最短路 / 判断两点是否相连

这是所有最短路算法里面最强大的最好写的也是唯一一个多源最短路算法，本质是DP。

核心思想是对于每两个点枚举第三个点，中转点，判断如果把路径改为经过这个点走是否变短，更新即可。

无法走到相当于无限长。

复杂度O(n3)，因为要用到三重循环。一般要求i,j,k不相等。

int dis[][];
//dis[i][j]表示从i点到j点的最短距离
void ini(){
    memset(dis,INF,sizeof(dis));
    for(int i=1;i<=n;++i)dis[i][i]=0;
    for(...){
        scanf("%d%d%d",&x,&y,&w);
        dis[x][y]=dis[y][x]=w; //无向图
        //dis[x][y]=w;有向图
    }
}
void floyd(){  
  for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<i;++j)
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
}

这里放一道题，利用了floyd的本质思想。

luoguP1119灾后重建

按时间顺序floyd。

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int x,y,w,n,m,Q,dis[203][203],t[203],nowfor=0,askt;
int main(){
    memset(dis,INF,sizeof(dis));
    for(int i=0;i<n;++i)dis[i][i]=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)scanf("%d",&t[i]);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&w);
        dis[x][y]=dis[y][x]=w;
    }scanf("%d",&Q);
    while(Q--){
        scanf("%d%d%d",&x,&y,&askt);
        if(t[x]>askt||t[y]>askt){printf("-1
");continue;}
        while(t[nowfor]<=askt&&nowfor<n){
            for(int i=0;i<n;++i)
                for(int j=0;j<n;++j)
                    dis[i][j]=min(dis[i][j],dis[i][nowfor]+dis[nowfor][j]);
             ++nowfor;
         }
         /*
　　　　　　　可以只用新节点来更新，因为更新新路径的时候他其实不是中转点
        */
        if(dis[x][y]!=INF)printf("%d
",dis[x][y]);
        else printf("-1
");
    }
    return 0;
}

Dijkstra : 不能处理负权图

朴素：O(N2) 
堆优化...（据说）手写二叉堆是O(elogv)，stl优先队列是O(eloge)，斐波那契堆是O(vlogv+e)，配对堆复杂度玄学

适用于稠密图（侧重于对点的处理）。

Dij的核心思想是从一个点出发，每次更新行走代价最小的那个点，也就是最近的那个点。注意已经在队列里的点还是会再走的，但出队的不会。(有点像Prim)

用vis数组维护每个点是否出队过(是否为蓝点)，已经出队的不再入队。每次取出一个点进行松弛。

朴素：穷举找最小值

堆优化：用优先队列维护最小代价。不能处理负环。运用蓝白点思想。

代码看例题，模版，堆优化。

luoguP4779单源最短路径

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e6+3;
struct Edge{
    int v,w,next;
}edge[N];
struct CMP{
    int dis,node;
    friend bool operator < (CMP a,CMP b){
        return a.dis>b.dis;
    }
};
int head[N],tot=0,dis[N],n,m,s;
bool vis[N]; //是否已经走过
void Add_edge(int u,int v,int w){
    edge[++tot]=(Edge){v,w,head[u]};
    head[u]=tot;
}
void dijk(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    priority_queue<CMP>Q;
    Q.push((CMP){0,s});
    dis[s]=0;
    while(!Q.empty()){
        int u=Q.top().node;
        Q.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v,w=edge[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v])Q.push((CMP){dis[v],v});
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    int u,v,w;
    while(m--){
        scanf("%d%d%d",&u,&v,&w);
        Add_edge(u,v,w);
    }
    dijk();
    for(int i=1;i<=n;++i)
        printf("%d ",dis[i]);
    return 0;
}

Bellman-Ford ： 不能处理负权回路

适用于稀疏图。

O(VE)的可怕复杂度....

每次穷举每条边看能否更新新的点的距离，直到结束。

好简略....

可以队列优化，其实就是SPFA，详见下一节。

SPFA : 不能处理负权回路  花里胡哨的优化一大堆

关于SPFA，他已经死了，不讲了

据说只要一个菊花图就能卡掉SPFA，总之很容易被卡。但是有个随机SPFA

复杂度上限O(NM) = O(VE)同朴素Bellman

一般复杂度为O(kE)(k为常数，均值为2) 但据说是错的。

 适用于稀疏图。

其实我觉得SPFA和Dijkstra很像....

但不用优先队列，普通队列即可。

用vis维护一个点是否在队列中，每次从队首取出一个点进行松弛。

如果新的点不在队列中就加入队列。

优化方法：

1.循环队列（可以降低队列大小） 

2.SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j) < dist(i)，则将j插入队首，否则插入队尾。（queue做不到系列）

3.LLL：Large Label Last 策略，对每个要出队的元素u，比较dis[u]和队列中dis的平均值，如果dis[u]更大，那么将它弹出放到队尾，取队首元素在进行重复判断，直至存在dis[x]小于平均值。

例题 luoguP3371单源最短路径

queue 普通的队列优化(455ms)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+3,INF=0x7fffffff;
struct Edge{
    int v,w,nt;
}e[N];
int n,m,s,dis[N],tot=0,head[N];
bool vis[N];
void Add(int u,int v,int w){
    e[++tot]=(Edge){v,w,head[u]};
    head[u]=tot;
}
void SPFA(){
    for(int i=1;i<=n;++i) dis[i]=INF;
    dis[s]=0;
    queue<int>Q;
    Q.push(s);
    vis[s]=true;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        vis[u]=false;
        for(int i=head[u];i;i=e[i].nt){
            int v=e[i].v,w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=w+dis[u];
                if(!vis[v]){
                    Q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,w);
    }
    SPFA();
    for(int i=1;i<=n;++i)printf("%d ",dis[i]);
    return 0;
}

deque双端队列优化（SLF）（452ms）

反正STL信不得（那去SAO啊艹）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+3,INF=0x7fffffff;
struct Edge{
    int v,w,nt;
}e[N];
int n,m,s,dis[N],tot=0,head[N];
bool vis[N];
void Add(int u,int v,int w){
    e[++tot]=(Edge){v,w,head[u]};
    head[u]=tot;
}
void SPFA(){
    for(int i=1;i<=n;++i) dis[i]=INF;
    dis[s]=0;
    deque<int>Q;
    Q.push_front(s);
    vis[s]=true;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop_front();
        vis[u]=false;
        for(int i=head[u];i;i=e[i].nt){
            int v=e[i].v,w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=w+dis[u];
                if(!vis[v]){
                    if(!Q.empty()&&dis[v]<dis[Q.front()])
                        Q.push_front(v);
                    else Q.push_back(v);
                    vis[v]=true;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,w);
    }
    SPFA();
    for(int i=1;i<=n;++i)printf("%d ",dis[i]);
    return 0;
}

SLF+LLL优化（440ms）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+3,INF=0x7fffffff;
struct Edge{
    int v,w,nt;
}e[N];
int n,m,s,dis[N],tot=0,head[N],SUM=0;
bool vis[N];
void Add(int u,int v,int w){
    e[++tot]=(Edge){v,w,head[u]};
    head[u]=tot;
}
void SPFA(){
    #define X ((double)SUM/(Q.size()+1))
    //出队了一个
    for(int i=1;i<=n;++i) dis[i]=INF;
    dis[s]=0;
    deque<int>Q;
    Q.push_front(s);
    vis[s]=true;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop_front();
        if(dis[u]>X){
            Q.push_back(u);
            continue;
        }
        vis[u]=false;
        for(int i=head[u];i;i=e[i].nt){
            int v=e[i].v,w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=w+dis[u];
                if(!vis[v]){
                    if(!Q.empty()&&dis[v]<dis[Q.front()])
                        Q.push_front(v);
                    else Q.push_back(v);
                    SUM+=dis[v];
                    vis[v]=true;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,w);
    }
    SPFA();
    for(int i=1;i<=n;++i)printf("%d ",dis[i]);
    return 0;
}

至于循环队列，请手写队列。

虽然好像优化不大...(其实几十ms完全没用....多测几次总有快有慢，评测误差)。

在大数据的时候还是有用的，而且对于LLL优化，手写队列更占优势，毕竟让deque多那么多push和pop可不是什么好事。

结论

  1. Floyed-Warshall算法，只有数据规模较小且时空复杂度都允许时才可以使用。
  2. Dijkstra算法，不能处理存在负边权的情况，侧重对点的处理，适用于：稠密图。
  3. Bellman-Ford算法，可以求出存在负边权情况下的最短路径，但无法解决存在负权回路的情况，侧重于对边的处理适用于：稀疏图。
  4. SPFA算法，侧重于对边的处理，适用于：稀疏图。

最后的话

　　如不能有效判断一个图是否稠密，建议使用堆优化dijkstra而不是SPFA，SPFA的时间复杂度不稳定且非常玄学。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lsy263/p/11400211.html