最短路径算法总结

其实这部分的内容我在之前的博客就记录了，今天闲来无事写来玩玩，没想到遇到这样那样的问题，自己去oj上提交一些代码居然还wa了几次，回顾一下吧

floyd算法
多源最短路径O(n^3)算法，原理很简单。由于复杂度高，所以n肯定不会多大，用邻接矩阵就够存了。

#include
using namespace std;
const int INF=1e9;
const int N=200;
int n,graph[N][N];
inline void floyd(){
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            if(graph[i][k]!=INF)
                for(int j=1;j<=n;++j)
                    if(graph[i][j]>graph[i][k]+graph[k][j])
                        graph[i][j]=graph[i][k]+graph[k][j];
    for(int s=1;s<=n;++s){
        for(int i=1;i<=n;++i)
            if(s==i)cout<<0<<" ";
            else if(graph[s][i]!=INF)cout<<graph[s][i]<<" ";
            else cout<<-1<<" ";
        cout<<endl;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            scanf("%d",&graph[i][j]);
            if(!graph[i][j])graph[i][j]=INF;
        }
    floyd();
}

dijkstra算法
单源最短路径算法，这是一种贪心的思维，贪心的策略是所有的点都有一个源点到改点的距离，每次都取距离最短的点，处理完这个点和邻接点以后不再处理该点，这一点用优先队列容易实现。

#include
using namespace std;
const int INF=1e9;
const int N=5e5+5;
struct edge{
    int from,to,w;
};
vector<edge>e[N];
struct s_node{
    int id,w;
    bool operator<(const s_node &s)const{return w>s.w;}
};
int n,m,s,dis[N],done[N];
inline void dijkstra(){
    for(int i=1;i<=n;++i)dis[i]=INF,done[i]=false;
    dis[s]=0;priority_queue<s_node>q;q.push({s,dis[s]});
    while(!q.empty()){
        s_node u=q.top();q.pop();
        if(done[u.id])continue;
        done[u.id]=true;
        for(int i=0;i<e[u.id].size();++i){
            edge y=e[u.id][i];
            if(done[y.to])continue;
            if(dis[y.to]>u.w+y.w){
                dis[y.to]=u.w+y.w;
                q.push({y.to,dis[y.to]});
            }
        }
    }

}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;++i){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        e[x].push_back({x,y,z});
    }
    dijkstra();
    for(int i=1;i<=n;++i)
        if(dis[i]!=INF)printf("%d ",dis[i]);
        else printf("%d ",(1<<31)-1);
}

Bellman_ford算法
这个算法的复杂度为O(n*m)，但是这个算法有一个dijkstra无法实现的功能：判断负环。
之前提到的dijkstra是对点进行松弛操作，并且利用队列对其进行了优化。而bellman_ford则是对边进行松弛操作。假设有n个点，那么最多进行n-1次松弛操作（对每条边来说，就拿该边的终点边来做松弛操作）肯定就能把源点到所有点的最短距离求出来了。那么我们再进行第n次松弛操作的时候，假设还有一些点的距离还能更短，那一定是因为存在了负权边，只有这样才可能。

模板算法：

#include
using namespace std;
const int N=1e5+5;
const int INF=1e9;
struct edge{
    int from,to,w;
}e[5*N+5];
int dis[N],n,m,s;
inline bool bellman_ford(){
    for(int i=1;i<=n;++i)dis[i]=INF;dis[s]=0;
    for(int i=1;i<n;++i){
        bool flag=false;
        for(int j=1;j<=m;++j){
            if(dis[e[j].to]>dis[e[j].from]+e[j].w){
                dis[e[j].to]=dis[e[j].from]+e[j].w;
                flag=true;
            }
        }
        if(!flag)break;
    }
    for(int j=1;j<=m;++j)
        if(dis[e[j].to]>dis[e[j].from]+e[j].w)return true;//存在负权边
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w);
    if(bellman_ford())cout<<"存在负权边"<<endl;
    else for(int i=1;i<=n;++i)printf("%d ",dis[i]);
}

SPFA算法
SPFA实际上是bellman_ford的队列优化算法，时间复杂度可以由之前的O（nm）优化到O（km），k是一个常量。
SPFA看似很无敌，但是在某些特定情况下也会被卡死，这点要注意一下。在最坏情况下，SPFA的算法复杂度和bellman_ford的O（n*m）是一样的。由于都是边松弛的算法，因此当然是边越少越好，也就是在面对稀疏图的时候，SPFA的效率是比较高的。

算法设计
（1）数据结构。由于是稀疏图，且点数很可能会给很大的时候我们会用SPFA，因此我们利用链式前向星来存储图，dis[i]记录从源点到节点i的最短路径长度，vis[i]标记节点i是否在队列中，sum[i]记录节点i入队次数（入队次数大于等于n的话一定有负环）。
（2）创建一个队列，源点u入队，标记u在队列中，u的入队次数加1。
（3）松弛操作。取出队头x，标记x不在队列中。考察x的所有出边i(x,v,w)，如果dis[v]>dis[x]+e[i].w，则进行松弛。如果结点v不再队列中，则如果v的入队次数+1后大于等于n，则说明有负环，退出；否则v入队，标记v在队列中。
（4）重复松弛操作，直到队列为空。

代码如下：

#include
using namespace std;
const int INF=1e9;
const int N=1e5+5;
struct edge{
    int to,w,next;
}e[5*N];
int head[N];//存储链式前向星中每个点的第一条边的编号
int n,m,s,cnt,sum[N],dis[N];
bool vis[N];
//vis数组用于标记是否在队列中，sum数组用于统计入队的次数
inline void add(int u,int v,int w){
    e[cnt].to=v,e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;//头插，指向第cnt条边
}
inline bool spfa(){
    memset(vis,false,sizeof(vis));memset(sum,0,sizeof(sum));
    queue<int>q;
    for(int i=1;i<=n;++i)dis[i]=INF;
    dis[s]=0;sum[s]++;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=false;
        for(int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    if(++sum[v]>=n)//存在负环
                        return true;
                    vis[v]=true;q.push(v);
                }
            }
        }
    }
    return false;
}
int main(){
    cin>>n>>m>>s;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;++i){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    if(spfa())cout<<"存在负权边"<<endl;
    else
        for(int i=1;i<=n;++i)
            if(dis[i]!=INF)printf("%d ",dis[i]);
            else printf("%d ",(1<<31)-1);
}

算法优化：SLF
如果待入队的节点是j，队首元素为节点i，若dis[j] 这种方法在随机数据上表现优秀，但是在正权图上的最坏情况为O(nm)，在负权图的最坏情况为达到指数级复杂度。

代码如下：

#include
using namespace std;
const int INF=1e9;
const int N=1e5+5;
struct edge{
    int to,w,next;
}e[2*N];
int head[N];//存储链式前向星中每个点的第一条边的编号
int n,m,s,cnt,sum[N],dis[N];
bool vis[N];
//vis数组用于标记是否在队列中，sum数组用于统计入队的次数
inline void add(int u,int v,int w){
    e[cnt].to=v,e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;//头插，指向第cnt条边
}
inline bool spfa(){
    memset(vis,false,sizeof(vis));memset(sum,0,sizeof(sum));
    deque<int>q;
    for(int i=1;i<=n;++i)dis[i]=INF;
    dis[s]=0;sum[s]++;q.push_front(s);
    while(!q.empty()){
        int u=q.front();q.pop_front();vis[u]=false;
        for(int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    if(++sum[v]>=n)//存在负环
                        return true;
                    vis[v]=true;
                    if(!q.empty()&&dis[q.front()]>dis[v])q.push_front(v);
                    //注意要判断队列是否为空
                    else q.push_back(v);
                }
            }
        }
    }
    return false;
}
int main(){
    cin>>n>>m>>s;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;++i){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    if(spfa())cout<<"存在负权边"<<endl;
    else
        for(int i=1;i<=n;++i)
            if(dis[i]!=INF)printf("%d ",dis[i]);
            else printf("%d ",(1<<31)-1);
}