單源最短路---所有邊權是正數(Dijkstra算法O(n^2)--稠密圖(鄰接矩陣)和堆優化的Dijkstra算法O(mlogn)--稀疏圖(鄰接表))?或存在負邊權(Bellman-ford貝爾曼福特算法O(nm)和SPFA一般O(m) 最壞O(nm)? )

多源最短路---Floyd算法O(n^3)

一、迪杰斯特拉算法(Dijkstra)：1dist[1]=0,dist[v]=正無窮。2for(v的0~n)，s是當前已經確定最短路徑的點，t是不在s中的距離最近的點，t放進s中，用t更新其他點的距離（dist[x]>dist[t]+w）更新。通過鄰接矩陣存圖。

#include<iostream>
#include<cstring> 
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];//確定最短路 
int dijkstra(){memset(dist,0x3f,sizeof(dist));dist[1]=0;//起點 for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;//找到dist最小的點 }if(t==n)break;//優化 st[t]=true;for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);}}if(dist[n]==0x3f3f3f3f)return -1;else return dist[n];
}
int main(){cin>>n>>m;memset(g,0x3f,sizeof(g));while(m--){int a,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c);}int t=dijkstra();cout<<t<<endl;return 0;
}

二、堆優化的迪杰斯特拉算法：優化在n個數中找距離最近的點O(n^2)用堆優化

#include<iostream>
#include<cstring> 
#include<queue> 
using namespace std;
typedef pair<int,int>PII;
const int N=150010;
int n,m;
int h[N],e[N],ne[N],idx,w[N];//權重 
int dist[N];
bool st[N];//是否已經確定最短路 
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(){memset(dist,0x3f,sizeof(dist));dist[1]=0;//起點 priority_queue<PII,vector<PII>,greater<PII>>heap;heap.push({0,1});//從1點開始,0為距離 while(heap.size()){auto t=heap.top();heap.pop();int ver=t.second,distance=t.first;if(st[ver])continue;st[ver]=true; for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>distance+w[i]){dist[j]=distance+w[i];heap.push({dist[j],j}); }}}if(dist[n]==0x3f3f3f3f)return -1;else return dist[n];
}
int main(){cin>>n>>m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c);}int t=dijkstra();cout<<t<<endl;return 0;
}

三、Bellman-Ford算法for循環n次，(備份)for所有邊a,b,w表示所有a到b的邊權值為w，(松弛)，處理有福權邊，能判斷是否有負環(但是一般用SPFA做)

• • 第?k?次松弛：找到經過最多?k?條邊的最短路徑。

• 通過多次松弛，算法可以逐步覆蓋從起點到所有節點的所有可能路徑

#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct Edge{int a,b,w;
}edges[M];
int bellman_ford(){memset(dist,0x3f,sizeof(dist));dist[1]=0;for(int i=0;i<k;i++){memcpy(backup,dist,sizeof(dist));for(int j=0;j<m;j++){int a=edges[j].a,b=edges[j].b,w=edges[j].w;dist[b]=min(dist[b],backup[a]+w);}}if(dist[n]>0x3f3f3f3f/2)return -0x3f3f3f3f;else return dist[n];
}
int main(){cin>>n>>m>>k;for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;edges[i]={a,b,c};}int t=bellman_ford();if(t==-0x3f3f3f3f)cout<<"impossible"<<endl;else cout<<t<<endl;return 0;
}

四、SPFA算法：用隊列，只要有變小就取出隊頭，更新t的所有出邊，成功就加入隊列（更新過誰就拿誰來操作）通過隊列優化 Bellman-Ford 算法，只對距離發生變化的節點進行松弛操作。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int N=100010;
int dist[N];
bool st[N];
int h[N],e[N],ne[N],idx,w[N];
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){memset(dist,0x3f,sizeof(dist));dist[1]=0;queue<int>q;q.push(1);st[1]=true;while(q.size()){int t=q.front();q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];if(!st[j]){q.push(j);st[j]=true;}}}}if(dist[n]==0x3f3f3f3f)return -0x3f3f3f3f;return dist[n];
}
int main(){cin>>n>>m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c);}int t=spfa();if(t==-0x3f3f3f3f)cout<<"impossible"<<endl;else cout<<t<<endl;return 0;
}

補充負環判斷：維護cnt[x]=cnt[t]+1，的數組，如果cnt[x]>=n存在負環。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010,M=10010;
int h[N],e[M],ne[M],idx,w[M];
int dist[N],cnt[N];
bool st[N];
int n,m;
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){queue<int>q;for(int i=1;i<=n;i++){q.push(i);st[i]=true;}while(q.size()){int t=q.front();q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];cnt[j]=cnt[t]+1;if(cnt[j]>=n)return true;if(!st[j]){q.push(j);st[j]=true;}}}}return false;
}
int main(){cin.tie(0),cout.tie(0);ios::sync_with_stdio(false);cin>>n>>m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c);}if(spfa())cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

五、Floyd算法：基于動態規劃三層for枚舉d(i,j)=min(d(i,j)，d(i,k)+d(k,j))。

#include<iostream>
#include<cstring> 
using namespace std;
const int N=210,INF=1e9;
int n,m,Q;
int d[N][N];
void floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}
}
int main(){cin>>n>>m>>Q;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)d[i][j]=0;else d[i][j]=INF;}}while(m--){int a,b,w;cin>>a>>b>>w;d[a][b]=min(d[a][b],w);}floyd();while(Q--){int a,b;cin>>a>>b;if(d[a][b]>INF/2)cout<<"impossible"<<endl;else cout<<d[a][b]<<endl;}return 0;
}