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