一些事情久久不能釋懷，於是最近學習了下最短路的演算法，希望我能變得輕鬆些。 dijkstra是一種單源最短路演算法。在沒有負權值的圖上，vi..vj..vk是vi到vk最短路的話，一定要走vi到vj的最短路。所以每次取出到起點距離最小的點，從該點出發更新鄰接的點的距離，如果更新成功則把新點加入prior ...
一些事情久久不能釋懷，於是最近學習了下最短路的演算法，希望我能變得輕鬆些。
dijkstra是一種單源最短路演算法。在沒有負權值的圖上，vi..vj..vk是vi到vk最短路的話，一定要走vi到vj的最短路。所以每次取出到起點距離最小的點，從該點出發更新鄰接的點的距離，如果更新成功則把新點加入priority_queue。儲存圖使用的是鄰接表。代碼如下：
#include <bits/stdc++.h>//有向圖 using namespace std; //dijkstra 不適用於帶負權的圖 const int maxn = 1007, maxm = 20007, INF = 2147483467;// maxn比頂點數略大，maxm比邊數略大 int head[maxn], vis[maxn], dis[maxn], fa[maxn]; int next[maxm], u[maxm], v[maxm], w[maxm]; typedef pair<int, int> pi;// pair排序策略是優先排前面，pair把距離放前面，點放後面 int n, m; void ini() { memset(vis, 0, sizeof(vis));//開始所有點都沒被處理 memset(head, -1, sizeof(head));//所有點都沒有邊 for(int i = 0; i <= n; i++) dis[i] = INF;//起點到所有點距離為無窮大 } void dij(int s, int e) { priority_queue<pi> Q;//優先隊列 dis[s] = 0; Q.push(make_pair(dis[s], s)); while(!Q.empty()) { pi u = Q.top(); Q.pop();//取出d最小的點 int x = u.second; if(x == e) break; if(vis[x])//處理過，跳過 continue; vis[x] = 1; for(int i = head[x]; ~i; i = next[i])//更新從當前d最小的點相鄰點的距離 { if(dis[v[i]] > dis[x] + w[i]) { dis[v[i]] = dis[x] + w[i];//鬆弛成功 fa[v[i]] = x; Q.push(make_pair(dis[v[i]], v[i]));//把更新成功的點加入隊列 } } } if(dis[e] == INF) return;//s到e無路徑 vector<int> ans;//用vector從終點往起點找路徑，也可以用遞歸 int temp = e; while(temp!=s) { ans.push_back(temp); temp = fa[temp]; } ans.push_back(s); for(int i = ans.size()-1; i >= 0; i--) printf("%d ", ans[i]); printf("\n%d\n", dis[e]); } int main() { //freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); ini(); for(int i = 0; i < m; i++) { scanf("%d%d%d", u+i, v+i, w+i); next[i] = head[u[i]]; head[u[i]] = i;//建立鄰接表 } int S, E;//起點終點 scanf("%d%d", &S, &E); dij(S, E); } return 0; }
dijkstra經典的一比，不過要求不能含負權，於是又學了下能處理帶負權圖的spfa：
spfa感覺有點像bfs，但bfs只處理一個節點一次，而spfa如果鬆弛了路徑上經過的節點，就要對路徑上之後的點都更新一遍。有負環的話，每走一遍負環，距離就減小環長，也就不存在最短路，所以假定不存在負環（或者判斷一下有無負環）。代碼如下：
#include <bits/stdc++.h>//有向圖 using namespace std; const int maxn = 1007, maxm = 10007, INF = 2147483467; int head[maxn], in[maxn], dis[maxn], fa[maxn];//in標記在queue中的點 int u[maxm], v[maxm], w[maxm], next[maxm]; int n, m; void ini() { memset(in, 0, sizeof(in)); memset(head, -1, sizeof(head)); for(int i = 0; i <= n; i++) dis[i] = INF; } void print(int s, int e)//遞歸列印路徑 { if(e!=s) print(s, fa[e]); printf("%d ", e); } void spfa(int s, int e)//有點像bfs，不過bfs不會處理之前處理過的點 { queue<int> Q; dis[s] = 0; in[s] = 1; Q.push(s); while(!Q.empty()) { int x = Q.front(); Q.pop(); in[x] = 0; for(int i = head[x]; ~i; i = next[i]) { if(dis[v[i]] > dis[x] + w[i]) { dis[v[i]] = dis[x] + w[i]; fa[v[i]] = x; if(!in[v[i]]) { Q.push(v[i]); in[v[i]] = 1; } } } } print(s, e); printf("\n%d\n", dis[e]); } int main() { freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); ini(); for(int i = 0; i < m; i++) { scanf("%d%d%d", u+i, v+i, w+i); next[i] = head[u[i]]; head[u[i]] = i; } int s, e; scanf("%d%d", &s, &e); spfa(s, e); } return 0; }
多源最短路徑有個floyd演算法，其實就是離散講的warshall閉包：（但是因為時間複雜度O（n^3）有點嫌棄2333），沒自己實現一下，核心代碼如下：
for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[i][k] + g[k][j];
思路是開始用鄰接矩陣存放圖，更新兩點距離只能靠經過其他點中轉，所以每次多允許經過一個點（即第一個迴圈），考慮最短路（第二三重迴圈）。
floyd好處是代碼短，能一次求出所有節點之間的最短路。
今天收穫挺大，總結一下稠密/無負權圖用dijkstra，稀疏/有負權圖用spfa，時間要求不高用floyd。
（心情依然很爛）
