前言
有一段时间没做最短路的题了，写题切实手生，于是我决定写下此篇模板，从原理登程，把原理刻在脑子里。
马上要较量了，我也告诫本人 思路决定前途，思维第一，绝不背诵代码
当然炽热的手感也是提速的要害，不背然而要纯熟，那就 每天起床第一步，先敲一遍最短路
最初面也放上我近期刷题的总结。
序
- 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，可能放弃自信。
之后我也将把刷到的陈腐的最短路问题进行记录下来，积攒思路，不便本人温习。
加油加油！为了上岸心仪的学校，冲啊！！！