前言
有一段時間沒做最短路的題了，寫題實在手生，於是我決定寫下此篇模板，從原理出發，把原理刻在腦子裏。
馬上要比賽了，我也告誡自己思路決定出路，思維第一，絕不背誦代碼
當然火熱的手感也是提速的關鍵，不背但是要熟練，那就每天起牀第一步，先敲一遍最短路
最後面也放上我近期刷題的總結。
序
- 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，能夠保持自信。
之後我也將把刷到的新鮮的最短路問題進行記錄下來，積累思路，方便自己複習。
加油加油！為了上岸心儀的學校，衝啊！！！
