胖虎的工具箱-编程导航 胖虎的工具箱-编程导航

最短路模板（dijkstra+spfa)~(链式向前星+邻接表)

2年前 (2022) 程序员胖胖胖虎阿
107 0 0

前言

有一段时间没做最短路的题了，写题实在手生，于是我决定写下此篇模板，从原理出发，把原理刻在脑子里。
马上要比赛了，我也告诫自己思路决定出路，思维第一，绝不背诵代码
当然火热的手感也是提速的关键，不背但是要熟练，那就每天起床第一步，先敲一遍最短路
最后面也放上我近期刷题的总结。

序

  • spfa+邻接表
  • spfa+链式向前星
  • dijkstra+邻接表
  • dijkstra+链式向前星

原理

最短路问题，属于图论问题，顾名思义就是求两点之间最短的路径。
我们用d[i]来表示i点到起点s的距离，求出起点到每个点的最短路径。

相同点: dijkstra和spfa其实都是bfs，都是从起点出发，逐层向外扩散，搜索最短距离然后逐层更新。
不同点：spfa逐层搜索的时候到某个点不一定是全局最短路，可能在之后搜索中发现通过其他点到这个点更近，所以那就再将这个点重新进入队列即可，再更新其他的点。像这样多次入队的点比较多的时候就会非常影响spfa的效率，所以spfa是不稳定的。

而dijkstra是非常稳定的，它在bfs的时候采用了优先队列，让每次push进队列的点都能排个序，当我们拿出来的时候自然就是最短的路径，每次用最短路更新后面的最短路即可。同时，这层的最短路去更新下一层的更大的最短路，也就决定了dijkstra的权值是非负的。

打模板的时候就尽量把所有的都加上，路径，判断负圈等。

比较一下这两种数据结构：经实践得到，邻接表已经能处理很大的图了，除非数据特别多那就用链式向前星，但是邻接表是更快一点，所以推荐使用邻接表（当然数据小能使用邻接矩阵肯定是最快的）
综上所述，权值非负一定是用dijkstra(稳),首选邻接表，数据特多用链式向前星。
更多细节我放到代码注释里。

spfa+邻接表：

  • 有负圈则选

    #include<bits/stdc++.h>
using namespace std;
int n,m,s;
const int inf=0x3f3f3f;
const int NUM=1e5;
int d[NUM];
bool inq[NUM];

int Neg[NUM];//判断负圈 
int pre[NUM];//记录路径 

struct edge{
    int from,to,w;
    edge(int a,int b,int c){
        from=a,to=b,w=c;
    }
};
vector<edge>e[NUM];//邻接表存图,一般喜欢以i点相邻的边来存。

void print_path(int s,int t){
    if(s==t){
        printf("%d ",s);
        return ;
    }
    print_path(s,pre[t]);//先打印前面的再打印后面的
    printf("%d ",t); 
} 
int spfa(int s){
    for(int i=1;i<=n;i++){//每个点初始化 
        d[i]=inf;inq[i]=false;
    }
    memset(Neg,0,sizeof(Neg));
    d[s]=0;inq[s]=true;Neg[s]=1;//自己到自己也算一个吧，所以为1，和后面的注释呼应 
    queue<int>q;//直接用点入队 
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=false;
        //这里和迪杰斯卡尔不一样,出了之后就false就行了，之后仍可访问 
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].to,w=e[u][i].w;
            //不像迪杰斯卡尔，这里无法判断continue
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                pre[v]=u;
                if(!inq[v]){//在队列里的就不能入队了，之前的都还没更完呢~ 
                    q.push(v);
                    inq[v]=true;
                    Neg[v]++;
                    if(Neg[v]>n){
                        return 1;//出现负圈 
                        //每个点到这个点的路加起来为n，如果有负圈，这个点最短路就无限更新。 
                    } 
                 }

            } 
        }
    }
    print_path(s,n);
    return 0; 
}
int main(){
    while(cin>>n>>m>>s){
    for(int i =1;i<=n;i++)e[i].clear();//清空 
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[a].push_back(edge(a,b,c));//一种存储方式罢了 
    }
    spfa(s);
    for(int i=1;i<=n;i++){//打印每个点最短路 
        printf("%d ",d[i]);
    }    
}
    return 0;
}

    spfa+链式向前星：

  • 负圈且图极大

    #include<bits/stdc++.h>
using namespace std;
const int NUM=1e5;
const int inf=INT_MAX/10; 

int n,cnt,m,s;
int head[NUM],d[NUM],pre[NUM],Neg[NUM];
bool inq[NUM];
struct edge{
    int next,to,w;
}e[NUM];//注意e[i]的i就是起点

void init(){
    for(int i=0;i<NUM;i++){//因为有初始化边，所以从0开始 
        head[i]=-1;
        e[i].next=-1;
    }
    cnt=0;
} 
void addedge(int u,int v,int w){
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];//链式向前，指向上一个u结点指向的head[u]的位置 
    head[u]=cnt++;//每次头节点取最大的位置 
} 
void print_path(int s,int t){
    if(s==t){
        printf("%d ",s);
        return ;
    }
    print_path(s,pre[t]);
    printf("%d ",t);
}
int spfa(int s){
    for(int i=1;i<=n;i++){
        d[i]=inf;
        inq[i]=false;
    }
    memset(Neg,0,sizeof(Neg));
    Neg[s]=1;d[s]=0;inq[s]=true;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=false;//已经在队列里面的,我们等会就不push
        for(int i=head[u];i!=-1;i=e[i].next){//从取出来的u点这一层，更新下一层 
            int v=e[i].to,w=e[i].w;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                pre[v]=u;
                if(!inq[v]){
                    q.push(v);
                    inq[v]=true;
                    Neg[v]++;
                    if(Neg[v]>n){
                        return -1;
                    }
                }
            }
        }

    } 
    print_path(s,n);
    return 0;
}
int main(){
    int a,b,c;
    while(cin>>n>>m>>s){
     for(int i=1;i<=n;i++)e[i].clear();
     init();//注意初始化 
     for(int i=1;i<=m;i++){
         scanf("%d%d%d",&a,&b,&c);
         addedge(a,b,c);//换了一种存储罢了
     } 
     spfa(s);
     for(int i=1;i<=n;i++){
         printf("%d ",d[i]);
     }
    }
     return 0;
}

    dijkstra+邻接表

  • 首选

    #include<bits/stdc++.h>
using namespace std;
const int inf=INT_MAX/10;
const int NUM=1e5;
int d[NUM];
int pre[NUM];
bool done[NUM];
int n,m,s;
struct edge{
    int from,to,w;
    edge(int a,int b,int c){
        from=a,to=b,w=c;
    }
};
vector<edge>e[NUM];
struct s_node{//s_node的主要目的是解决spfa不稳定的问题,我们用了优先队列 
//它将每个点到起点s的距离排序，从而bfs的时候每次都是
//向外层 扩散都是以最小距离扩散 ，能稳定地得到最短路径。 
    int id;int s_d;
    s_node(int b,int c){
        id=b,s_d=c;
    } 
    bool operator<(const s_node&a)const{//排序的方式 
        return s_d>a.s_d;//默认为大顶堆 
    }
};
void print_path(int s,int t){
    if(s==t){
        printf("%d ",s);
        return ;
    }
    print_path(s,pre[t]);
    printf("%d ",t);
}
void dijkstra(int  s){
    //就是一个把点分为队列里面和队列外面的 bfs
    //最开始队列里面只有s，每次去外面找到和队列里的点最短的边的终点
    //然后放进队列里面，然后层层更新最短的边，每次都是最短，所以稳定 
    for(int i=1;i<=n;i++){
        d[i]=inf;done[i]=false;
    }
    d[s]=0;
    priority_queue<s_node>q;//优先队列 
    q.push(s_node(s,d[s]));
    while(!q.empty()){
        int u=q.top().id;q.pop();//top 
        if(done[u])continue;//已经在队内了，即访问了最短路的点就不用管了
        done[u]=true;//最短路径的点说明放入到队内拉 
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].to,w=e[u][i].w;
            if(done[v])continue;//同样已经在队内就不用管了
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                pre[v]=u; 
                q.push(s_node(v,d[v]));//每个点只访问一次，所以肯定push和spfa不一样 
            } 
        } 
    } 
    print_path(s,n);
}
int main(){
    while(cin>>n>>m>>s){    
    int a,b,c;
    for(int i=1;i<=n;i++)e[i].clear();
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        e[a].push_back(edge(a,b,c));
    } 
    dijkstra(s);
    for(int i=1;i<=n;i++){
        printf("%d ",d[i]);
    } 
}
    return 0;
}

    dijkstra+链式向前星：

  • 无负圈且图巨大

    #include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;
const  int NUM=1e5;
int n,m,s,cnt;
bool done[NUM];
int d[NUM],head[NUM],pre[NUM];
struct edge{
    int next,to,w;
}e[NUM];//e[i]的i就是起点 

void init(){
    for(int i=0;i<NUM;i++){
        e[i].next=-1;
        head[i]=-1;
    }
    cnt=0;
}
void addedge(int u,int v,int w){
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
void print_path(int s,int t){
    if(s==t){
        printf("%d ",s);
        return ;
    }
    print_path(s,pre[t]);
    printf("%d ",t);
}
struct s_node{
    int id,s_d;
    s_node(int b,int c){
        id=b,s_d=c;
    }
    bool operator<(const s_node&a)const {
        return s_d>a.s_d;
    }
};
void  dijkstra(int s){
    for(int i=1;i<=n;i++){
        d[i]=inf;done[i]=false;
    }
    d[s]=0;
    priority_queue<s_node>q;
    q.push(s_node(s,d[s]));
    while(!q.empty()){
        int u=q.top().id;q.pop();
        if(done[u])continue;
        done[u]=true;
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].to,w=e[i].w;
            if(done[v])continue;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                q.push(s_node(v,d[v])); 
            }
        }
    } 
}
int main(){
    while(cin>>n>>m>>s){
        //e[i]不用clear，因为有init（） 
        init();
        int a,b,c;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
        }
        dijkstra(s);
        for(int i=1;i<=n;i++){
            printf("%d ",d[i]);
        }
}
    return 0;
}

近期刷题总结：debug能力太差，非常依赖题解，接下里的刷题日子里希望自己能独立debug，能够保持自信。
之后我也将把刷到的新鲜的最短路问题进行记录下来，积累思路，方便自己复习。
加油加油！为了上岸心仪的学校，冲啊！！！

版权声明：程序员胖胖胖虎阿 发表于 2022年9月5日 上午7:00。
转载请注明：最短路模板（dijkstra+spfa)~(链式向前星+邻接表) | 胖虎的工具箱-编程导航

相关文章

java程序员面试题大全含答案（2018--2019）
程序员胖胖胖虎阿
267
IDEA最新 激活码(IntelliJ IDEA2021永久激活码激活至2099年)
程序员胖胖胖虎阿
88
Skywalking概述
程序员胖胖胖虎阿
279
IntelliJ IDEA2022.2 激活码(Intellij IDEA最新激活码,激活至2099年)
程序员胖胖胖虎阿
371
IDEA安装及注册码(IDEA最新破解图文教程,最新有效IDEA激活码)
程序员胖胖胖虎阿
181
IDEA全新激活码激活教程(windows/mac idea最新永久永久激活码成功激活)
程序员胖胖胖虎阿
96

暂无评论

暂无评论...
致力于称为最好的程序员导航网站

友链申请 免责声明 关于我们

Copyright © 2022  胖虎的工具箱-编程导航   陇ICP备2022001249号