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

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

2年前 (2022) 程序员胖胖胖虎阿
174 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)~(链式向前星+邻接表) | 胖虎的工具箱-编程导航

相关文章

IDEA全新 激活码(IDEA最新版 破解教程,全年更新)
程序员胖胖胖虎阿
255
IntelliJ IDEA安装及 激活码(IntelliJ IDEA2020激活码,成功激活)
程序员胖胖胖虎阿
154
java面试笔试题50道及答案
程序员胖胖胖虎阿
409
IDEA最新永久激活码(Intellij IDEA2022永久激活码永久有效)
程序员胖胖胖虎阿
343
IntelliJ IDEA专业版 破解教程(IDEA最新破解版永久有效)
程序员胖胖胖虎阿
217
认识Java中的类和对象（上）
程序员胖胖胖虎阿
643

暂无评论

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

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

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