关于算法:最短路模板dijkstraspfa链式向前星邻接表

43次阅读

共计 5460 个字符,预计需要花费 14 分钟才能阅读完成。

前言

有一段时间没做最短路的题了,写题切实手生,于是我决定写下此篇模板,从原理登程,把原理刻在脑子里。
马上要较量了,我也告诫本人 思路决定前途,思维第一,绝不背诵代码
当然炽热的手感也是提速的要害,不背然而要纯熟,那就 每天起床第一步,先敲一遍最短路
最初面也放上我近期刷题的总结。

  • 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,可能放弃自信。
之后我也将把刷到的陈腐的最短路问题进行记录下来,积攒思路,不便本人温习。
加油加油!为了上岸心仪的学校,冲啊!!!

正文完
 0