# 最短路徑 ---- ## 術語 ---- ## 負邊 權重為負的邊 ---- ## 負環 權重和為負的環 ---- ## 點源(Source) 成為起點的點，分成單源頭(Single Source)及多源頭(Multiple Source)。 ---- ## 鬆弛(Relax) 現在要找尋起點為 s 、終點為 t 的最短路徑，而且現在已經有一條由 s 到 t 的路徑，這條路徑上會依序經過 a 及 b 這兩點（可以是起點和終點）。我們可以找到一條新的捷徑，起點是 a 、終點是 b 的捷徑，以這條捷徑取代原本由 a 到 b 的這一小段路徑，讓路徑變短。 ---- ## 單點源最短路徑(Single Source) ---- ## Dijkstra's Algorithm ---- * 把離樹根最近的點加入最短路徑樹裡 * 並把所有與該點相連的邊鬆弛 * 已經加入的點不會在被鬆弛 * 使用priority_queue的複雜度為$O((V+E)logE)$ * [example](http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dijkstra.html) ---- * $d[n]$ 到n的距離 * $edge[node.from][node.to]$ $node.from$ 與 $node.to$ 之間的邊長度 ```cpp= if(d[node.to] > d[node.from] + edge[node.from][node.to]){ d[node.to] = d[node.from] + edge[node.from][node.to]; q.push({node.to,d[node.to]}); } ``` ---- ```cpp= struct edge{ int from,to,w; }; struct Node{ int node,dist; P(int _node,int _dist){ node = _node; dist = _dist; } bool operator<(const P& rhs)const{//權重較小的邊與點源距離較大 return dist > rhs.dist; } }; vector<edge>edges; vector<int>G[20001]; int d[20001],Case,n,m,s,e,from,to,w,cnt; void addedge(int from,int to, int w){//建雙向邊 edges.push_back({from,to,w}); edges.push_back({to,from,w}); int m = edges.size(); G[from].push_back(m-2);//存與from相連的邊在edges的index G[to].push_back(m-1); } bool vis[20001];//是否拜訪過 void init(){ edges.clear(); for(int i=0;i<20001;i++){ G[i].clear(); d[i] = inf;//距離皆設無限大 vis[i] = false; } d[s] = 0;//起點距離為0 } void dijkstra(){ priority_queue<Node>q; q.push(Node(s,d[s])); while(!q.empty()){ auto x = q.top();q.pop(); if(x.node == e)break; if(vis[x.node])continue;//已經拜訪過則skip vis[x.node] = true; for(auto it:G[x.node]){//找與G[x.node]相鄰點的index auto edge = edges[it];// if(d[edge.to] > d[edge.from] + edge.w){ d[edge.to] = d[edge.from] + edge.w; q.push({edge.to,d[edge.to]}); } } } } ``` ---- [遇到負邊會發生甚麼事?](https://www.itread01.com/content/1548100475.html) ---- ## 題單 * [uva 929](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=870) * [uva 10986](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1927) ---- ## [Bellman–Ford algorithm](https://ithelp.ithome.com.tw/articles/10209748) ---- 因為拜訪過就不考慮進去 ---- 那麼就... ---- 不管你有沒有拜訪過都考慮進去 ---- * 單點源最短路徑 * 對所有邊枚舉，執行V-1輪(因為最短路徑上最遠的兩個點經過V-1條邊)，複雜度為$O(VE)$ * 如果執行第V次時還有邊可以鬆弛，代表有負環 * [example](https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/) ---- ```cpp= void bellman_ford(int s){ d[s]=0; p[s]=s; for(int i=0;i<V-1;i++){//進行V-1次鬆弛 for(int ss=0;ss<V;ss++){ for(auto tt:v[ss]){//與ss相連的邊 if(d[ss]+w[ss][tt]<d[tt]){ d[tt]=d[ss]+w[ss][tt]; p[tt]=ss; } } } } } bool has_negative_cycle(){ for(int i=0;i<V;i++){ for(int j=0;j<V;j++){ if(d[i]+w[i][j]<d[j])return true; } } return false; } ``` ---- ## 題單 * [uva 558](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=499) * [uva 10449](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1390) ---- [先備知識](https://www.itread01.com/content/1547221357.html) ---- ## [Floyd Warshall Algorithm](https://ithelp.ithome.com.tw/articles/10209186) ---- **求任意兩點之間最短路徑** ---- 概念:因為每一個點都有可能使另外兩個點之間的路徑變的更短，所以就把所有的點當作中間點枚舉 ---- ## DP式 * 狀態：$dp[k][i][j]$ 代表,若只以點 1到k 當中繼點的話,則 $dp[k][i][j]$ 為 i 到 j 的最短路徑長。 * 轉移：$dp[k][i][j]$ = min($dp[k-1][i][k]$ + $dp[k-1][k][j]$, $dp[k-1][i][j]$) * 基底： $dp[0][i][j]$ = $w[i][j]$ if $w[i][j]$ exists INF else ---- ```cpp= for (k = 0; k < n; k++)//枚舉中間點 for (i = 0; i < n; i++)//枚舉起點 for (j = 0; j < n; j++)//枚舉終點 w[k][i][j] = min(w[k-1][i][j], w[k-1][i][k] + w[k-1][k][j]);//雙向邊 w[i][j] = w[j][i] = min(w[i][j], w[i][k] + w[k][j]);//單向邊 ``` ---- * 時/空間複雜度皆為$O$(V^3^) * 滾動陣列 * 空間複雜度可降為$O$(V^2^) ---- ## 空間壓縮 ```cpp= for (k = 0; k < n; k++)//枚舉中間點 for (i = 0; i < n; i++)//枚舉起點 for (j = 0; j < n; j++)//枚舉終點 w[i][j] = min(w[i][j], w[i][k] + w[k][j]);//雙向邊 w[i][j] = w[j][i] = min(w[i][j], w[i][k] + w[k][j]);//單向邊 ``` ---- $dp[i][j]<0$ 代表存在負環