# 最短路徑演算法 --- ## 問題敘述 * 給定一個帶權圖G，求一條路徑讓S到T的權重總和最小。 * 有兩種題型 * 全點對 * 單點源 --- ## Floyd Warshall * 全點對最短路徑演算法 * 好寫 * 動態規劃 ---- ## 提出者 * Robert W．Floyd * 不是理科專業而是文組 * 以heapsort獲得1980年的圖靈獎 ---- ## 鬆弛(Relax) $dist[s][t]=min(dist[s][t],dist[s][k]+dist[k][t])$ ---- ## DP * 設dp[i][j][k]為從i到j使用前k個點進行鬆弛後的最短路徑 * 如果k鬆弛可以更短$dp[i][j][k]=dp[i][k][k-1]+dp[k][j][k-1]$ * 如果無法更短$dp[i][j][k]=dp[i][j][k-1]$ * $dp[s][t]=min(dp[s][t],dp[s][k]+dp[k][t])$ ---- ## 時間複雜度 $O(n^3)$ ---- ## code ```cpp= #include<bits/stdc++.h> #define ll long long using namespace std; int mp[1005][1005]; void floyd_wharshall(int n){ for(int k=0;k<n;++k) for(int i=0;i<n;++i) for(int j=0;j<n;++j) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); } int main(){ memset(mp,0x3f,sizeof(mp)); int n,m;cin>>n>>m; for(int i=0;i<m;++i){ int a,b,w; cin>>a>>b>>w; mp[a][b]=w;mp[b][a]=w; } for(int i=0;i<n;++i)mp[i][i]=0; floyd_wharshall(n); return 0; } ``` --- ## Bellman Ford * 單點對最短路 * 支持負邊權 * 可尋找負環 ---- ## 提出者 * Richard Bellman 和 Lester Randolph Ford Jr. 以及 Edward F. Moore * Richard Bellman :動態規劃的創始人 * Lester Randolph Ford Jr. : 確立了最大流量最小割定理 * Edward F. Moore :人工智慧先驅 ---- ## 鬆弛(Relax) * 設dist[t]為u到t的最短路 * $dist[t]=min(dist[t],dist[v]+len[v][t])$ ---- ## 過程 * 每條邊都試一遍，一定能找到一條邊進行鬆弛 * 如果無法鬆弛，演算法便停止 * 如果每條邊都鬆弛過卻還能鬆弛->有負環 ---- ## 時間複雜度 $O(n^2)$ ---- ```cpp= struct data{ int a,b,w; }edge[100005]; ll dist[100005]; void bellman_ford(int n,int m){ memset(dist,0x3f,sizeof(dist)); for(int i=0;i<n;++i){ bool valid=0; for(int j=0;j<m ;++j){ if(dist[edge[j].a]>dist[edge[j].b]+edge[j].w){ dist[edge[j].a]=dist[edge[j].b]+edge[j].w; valid=1; } if(dist[edge[j].b]>dist[edge[j].a]+edge[j].w){ dist[edge[j].b]=dist[edge[j].a]+edge[j].w; valid=1; } } if(!valid)return; if(i==n-1){ cout<<"negative\n"; return; } } } ``` ---- ## code ```cpp= #include<bits/stdc++.h> #define ll long long using namespace std; struct data{ int a,b,w; }edge[100005]; ll dist[100005]; void bellman_ford(int n,int m){ memset(dist,0x3f,sizeof(dist)); for(int i=0;i<n;++i){ bool valid=0; for(int j=0;j<m ;++j){ if(dist[edge[j].a]>dist[edge[j].b]+edge[j].w){ dist[edge[j].a]=dist[edge[j].b]+edge[j].w; valid=1; } if(dist[edge[j].b]>dist[edge[j].a]+edge[j].w){ dist[edge[j].b]=dist[edge[j].a]+edge[j].w; valid=1; } } if(!valid)return; if(i==n-1){ cout<<"negative\n"; return; } } } int main(){ int n,m;cin>>n>>m; for(int i=0;i<m;++i){ cin>>edge[i].a>>edge[i].b>>edge[i].w; } bellman_ford(n,m); return 0; } ``` --- ## Dijkstra * 單點對最短路 * 不支持負邊權 * 最快的演算法 ---- ## 提出者 * Edsger Wybe Dijkstra * 荷蘭人 * 以結構化編程和程式語言科學化獲得1972年圖靈獎 * 和演算法之父Donald Ervin Knuth並稱這世代最偉大的電腦科學家 ---- ## 過程 * 設置一集合S代表走過的點 * 找到一條權重最小的邊連結集合中的一點和未在集合中的一點 * 重複執行直到所有點都走過 ---- ## 時間複雜度 $O(n^2)$ ---- ## 優化 * 使用heap找最小權重之邊 * $O(n^2)->O(nlogn)$ ---- ```cpp= #define ll long long #define ff first #define ss second #define mp make_pair vector<pair<int,ll>> v[100005]; ll dist[100005]; void dijkstra(int u){ memset(dist,0x3f,sizeof(dist)); priority_queue<pair<ll,int> > pq; pq.emplace(0,u); while(!pq.empty()){ auto tmp=pq.top();pq.pop(); if(dist[tmp.ss]!=0x3f3f3f3f3f3f3f3f)continue; dist[tmp.ss]=-tmp.ff; for(auto e:v[tmp.ss]) pq.emplace(-(e.ss-tmp.ff),e.ff); } } ``` ---- ## code ```cpp= #include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define mp make_pair using namespace std; vector<pair<int,ll>> v[100005];//存圖 ll dist[100005];//存原點到各點的最短路 void dijkstra(int u){ memset(dist,0x3f,sizeof(dist));//初始化 priority_queue<pair<ll,int> > pq; pq.emplace(0,u); while(!pq.empty()){//重複執行直到所有點都走過 auto tmp=pq.top();pq.pop(); if(dist[tmp.ss]!=0x3f3f3f3f3f3f3f3f)continue; dist[tmp.ss]=-tmp.ff; for(auto e:v[tmp.ss]) pq.emplace(-(e.ss-tmp.ff),e.ff); } } int main(){ int n,m;cin>>n>>m; for(int i=0;i<m;++i){ int a,b,w; cin>>a>>b>>w; v[a].emplace_back(mp(b,w)); v[b].emplace_back(mp(a,w)); } int s,t;//尋找s~t的最短路 cin>>s>>t; dijkstra(s); cout<<dist[t]<<'\n'; return 0; } ``` ---