# Ch20 最短路徑 - DIJKSTRA > 搭配 [virtual judge解題系統](https://vjudge.net/contest/276600) ## > 上一章：[BFS廣度優先搜尋](https://hackmd.io/s/BkxmExS8J4) > 下一章：[並查集 Disjoing set (Union find)](https://hackmd.io/s/rkRVS_o-4) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## <font color='darkblue'>甚麼情況需要用到最短路徑</font> ![](https://i.imgur.com/8wor4Tp.png) 這是上一單元的圖 從藍色走到紅色最快的走法 也就是走最少格子的走法 我們在上一章學會用BFS來解決 ![](https://i.imgur.com/dD7OcwP.png) 那麼這章 我們來讓題目變得更複雜： 每一格都有「過路費」 你要找的不是「經過最少格子的走法」 而是「需要付最少過路費的走法」 ![](https://i.imgur.com/adTHQCO.png) 如圖，每一格上面的數字代表的是那格的過路費 這題的正解為灰色那條路 代表的是過路費最低的走法 ![](https://i.imgur.com/CaudNuV.png) 同樣都是能走的路 我們必須選擇過路費較低的格子走 甚至也有可能出現要「繞路」比較划算的情況 ![](https://i.imgur.com/6k5V1v6.png) 在這個案例中 儘管它好像繞了遠路、走了較多格子 但以下這走法是最划算的 ![](https://i.imgur.com/vSWcUrb.png) 那麼究竟怎麼在給定的題目中 找到花最少錢的走法呢? 這就是這一章要教的 「最短路徑演算法」 ## <font color='darkblue'>最短路徑演算法-dijkstra</font> 用來解決這種問題的演算法有很多流派 各有各的長處 >有的可以拿來算出所有點兩兩之間的最短距離 >有的專門拿來算特定起點到每一點的最短距離； >有的不能處理路徑長為負數的案例 >有的可以處理負數路徑還能順便偵測負環 這一章要介紹的是dijkstra演算法 因為它和BFS很像 不要問我dijkstra怎麼念 我都念dijkstra 接下來示範如何用dijkstra演算法 逐一算出從起點走到每一格所需要的最小花費 ![](https://i.imgur.com/bJTDHTw.png) 首先 到達左下角格子所需要的最小花費是4 這點是肯定的 因為它就是起點了 沒有其他走法可以有更小的花費了 我們用紅色來代表已經肯定的答案 ![](https://i.imgur.com/6WjFugh.png) 接下來 起點的上方與右邊的「暫時答案」都可以從起點的答案推出來 為何說是「暫時」呢 因為還有可能有繞遠路的走法來讓答案更小 因此先用綠色代表「我暫時發現這格目前的答案是5」、「我暫時發現這格目前的答案是13」 接下來 我們要在所有的綠色裡面 選一個最小的值 把他變成「肯定的紅色」 <font color='red'>因此它已經是目前已知的最近格子了 已經不可能透過繞遠路來讓它變得更近</font> (↑這概念不好懂，但是是核心觀念哦，有問題請盡量質疑！而且這只適用於「沒有負的過路費」的情況！) ![](https://i.imgur.com/AJlXZOR.png) 把左上方的5變成「肯定的答案」的同時 要順便透過它來找出它上下左右的答案 這時我們算出他右邊的答案是7 ![](https://i.imgur.com/CXd3u6T.png) 再來一樣是從所有綠色的格子裡面選數字最小的那個變成紅色 再把它的上下左右格子也找出答案 ![](https://i.imgur.com/LIMxUzp.png) ![](https://i.imgur.com/pFePwCe.png) 一直這樣標下去 直到終點的格子也變成紅色 就可以確定答案了 問題來了 剛才每次都在所有的綠格子中找數字最小的 可是要怎麼最有效率地找呢? 把所有格子都看過一遍找最小的一定會超時 希望有個神奇袋子可以每次都把最小的數字浮上來給我 甚麼樣的袋子可以做到這樣的事情呢? ## <font color='darkblue'>dijkstra的好朋友 - priority queue</font> 上上個單元在教stack與queue的時候 最後面有順便講到priority queue priority queue的行為是這樣的 你把一堆數字丟進去 他會把最大的數字放在它的頂端 當你把一個數字pop掉時 它會自動調整裡面剩下的數字 把剩的裡面最大的移到頂端 當你把新數字丟進去時 它也會自動把新數字喬到它該去的位置 不過在這個題目中 我們有一些特別的要求 1. 希望每次拿到的是最小的數字 2. 希望這個數字能夠跟它格子的座標綁在一起放在袋子裡 首先先介紹怎麼把資料給綁在一起 上次是使用pair 這次介紹「struct」 不過基本上用途是類似的 struct相當一個盒子 你要把這個盒子取一個名稱 在這裡我把它取名為"cell" 記得把它宣告在main的外面 ```cpp= struct cell { int r; int c; int dis; }; int main() { cell A = {0,0,5}; cell B = {1,2,3}; cell C = {2,4,1}; } ``` 如上述的寫法 我就會有名為A、B、C的三個cell 其中A的r是0，A的c是0，A的dis是5 B的r是1，B的c是2，B的dis是3...以此類推 我們可以用"."這個符號來取struct裡面的資料 ```cpp= cout<<A.r<<endl; //印出0 cout<<C.dis<<endl; //印出3 int q = B.c; //q變為2 ``` 有了這樣的盒子 我們就可以把座標和它的答案綁起來了 最後一步是要能把這盒子放進priority_queue裡面 並且要求它「把dis最小的放最上面」 想要讓它把dis最小的放最上面 我們需要在宣告struct cell的時候加上這一段 ```cpp= struct cell { int r; int c; int dis; bool operator<(const cell& rhs) const { return dis<rhs.dis; } }; ``` 定義兩個cell之間比大小會用什麼來比 這個的意思是說，我們要用cell裡面的dis的大小關係來決定cell之間的大小關係 還有一點麻煩的事情 就是 priority_queue 預設為「最大的放在最上面」 但現在我們需要「最小的放在最上面」 因此在宣告 priority_queue 的時候 我們需要宣告成： ```cpp priority_queue<cell, vector<cell>, greater<cell> > pq; ``` 這樣一來可以示範整段prioiry_queue的用法了 ```cpp= struct cell { int r; int c; int dis; bool operator<(const cell& rhs) const { return dis<rhs.dis; } }; int main() { cell A = {0,0,5}; cell B = {1,2,3}; cell C = {2,4,1}; priority_queue<cell, vector<cell>, greater<cell> > pq; pq.push(A); pq.push(B); pq.push(C); cell TOP = pq.top(); cout<<TOP.r<<" "<<TOP.c<<" "<<TOP.dis<<endl; //印出2 4 1 } ``` 學會priority_queue怎麼使用後 可以來看看整個程式碼了 ## <font color='darkblue'>寫dijkstra的程式</font> 一開始先把每一格的答案都先洗成999999999 (一定要夠大，但也不能超過int的範圍) 這樣一來就可以在每次找到更近的路時取代舊答案 也順便把每一格都標上「不是紅色」 ```cpp= for(int i=0;i<1000;i++){ for(int j=0;j<1000;j++){ ans[i][j]=999999999; red[i][j]=0; } } ``` 首先，起點可以先標上答案了 起點的答案就是起點那格的花費 並且把起點的座標與答案綁在一起 丟進priority_queue裡 ```cpp= ans[start_x][start_y]=cost[start_x][start_y]; cell start={start_x, start_y, cost[start_x][start_y]}; pq.push(start); ``` 接下來要不斷從priority_queue裡面拿新的數字出來 1.如果它已經是紅色了就跳過 2.把它變紅色 3.如果新答案比目前答案還要好的話，把它的上下左右都標上新答案 ```cpp= while(!pq.empty()) { cell cur=pq.top(); pq.pop(); int x=cur.r; int y=cur.c; int dis=cur.dis; // 如果他已經是紅色了，就跳過 if(red[x][y]==1) continue; // 把它標為紅色 red[x][y]=1; // 試著把它的上下左右鄰居變小 for(int i=0;i<4;i++){ int new_x=x+dx[i]; int new_y=y+dy[i]; if(new_x和new_y都沒超界){ //如果新答案比舊答案好，就把它取代掉 if(ans[new_x][new_y]>dis+cost[new_x][new_y]){ ans[new_x][new_y]=dis+cost[new_x][new_y]; cell next={new_x, new_y, ans[new_x][new_y]}; pq.push(next); } } } } ``` 最後只要印出終點那格的答案就好了~ <font color="darkgreen"> 【學生練習題】</font> > - [ ] [A - Number Maze ](https://vjudge.net/contest/276600#problem/A) ## <font color='darkblue'>站與路相連的世界</font> 上一章的BFS 與剛才的例子 都是在格子世界中發生的 然而這世界哪有這種格子結構呢 反而像是鐵路、飛機 大多都是「站與路」的結構 因此接下來要介紹「站與路」的結構要怎麼算出最短路徑 ![](https://i.imgur.com/Q8v4BEX.png =300x) 如圖就是站與路的結構 我們稱之為「Graph」(圖) 其中點與點之間可能會有路相接 現在假設每條路都有自己的過路費 我們用綠色的數字代表那條路的過路費 ![](https://i.imgur.com/1GN8ndo.png =400x) 題目可能會說是過路費 也可能會說是通過這條路所要花掉的時間 總之都是「花費成本」的概念，我們用「cost」來代稱 為了表達方便，我們通常會在每個點加上編號 ![](https://i.imgur.com/AE9QyWv.png =400x) 這樣一來可以出很多問題 以這章來舉例的話 可以問你「0號點至4號點的最短距離是多少呢?」 ## <font color='darkblue'>站與路相連的世界 - 資料結構</font> 為了表達一張圖 題目會告訴你總共有幾個點、幾條路 並且給你每一條路的資訊： 它是連接哪兩個點，以及它的cost是多少 例如在這張圖中 會輸入6 6，代表6個點，6條邊 接下來有六行告訴你每條路的資訊 ``` 0 1 2 //0和1之間有條路，cost為2 1 3 3 //1和3之間有條路，cost為3 1 5 5 //1和5之間有條路，cost為5 3 5 1 //3和5之間有條路，cost為1 5 4 2 //5和4之間有條路，cost為2 3 2 2 //3和2之間有條路，cost為2 ``` 所以我們要用陣列把每一點相鄰的邊存起來 這邊的陣列我推薦用vector 它的用法跟陣列相似 你可以想像成「伸縮陣列」 也就是你存了多少東西進去，它的size就有多大 ## <font color='darkblue'>伸縮陣列 - vector</font> 首先介紹vector如何使用 假設你的vector是拿來存int的 並且取名為vv 你可以宣告成 ```cpp= #include<vector> vector<int> vv; ``` 現在這個vv的size是0 你可以塞東西進去了 你塞幾個他的size就是多少 ```cpp=4 vv.push_back(3); vv.push_back(4); vv.push_back(1); ``` 這時他的size就是3了 可以像取陣列的值一樣把裡面的東西都拿出來看 ```cpp=7 for(int i=0;i<vv.size();i++){ cout<<vv[i]<<endl; } ``` 當然也可以宣告一個「vector的陣列」 ``` vector<int> vv[5]; vv[0].push_back(3); //vv[0][0]=3 vv[0].push_back(1); //vv[0][1]=1 vv[1].push_back(4); //vv[1][0]=4 ``` 那在剛才的題目中 我們就可以宣告兩個vector的陣列 分別來存每個點的「鄰居有誰」 以及「連到該鄰居的路的cost」 ```cpp= vector<int> neighbor[100]; vector<int> cost[100]; int node, road; cin>>node>>road; for(int i=0;i<road;i++){ int n1, n2, c; cin>>n1>>n2>>c; //n1的鄰居有n2，且路的長度為c neighbor[n1].push_back(n2); cost[n1].push_back(c); //n2的鄰居有n1，且路的長度為c，但如果題目說這條路是單行道，這兩行就不可以寫了 neighbor[n2].push_back(n1); cost[n2].push_back(c); } ``` 你可以隨意印東西出來看看 ```cpp= cout<<"node 0 has "<<neighbor[0].size()<<" neighbors"<<endl; for(int i=0;i<neighbor[0].size();i++){ cout<<"one of his neighbor is "<<neighbor[0][i]<<endl; cout<<"their road costs "<<cost[0][i]<<endl; } ``` ## <font color='darkblue'>站與路相連的世界 - 找出最短路徑</font> ![](https://i.imgur.com/AE9QyWv.png =400x) 起點是0號 請問起點至4號點的最短距離為多少呢? 這一樣可以使用dijkstra來解決 首先，起點的距離為0，肯定的 ![](https://i.imgur.com/RbJmhJ4.png =400x) 接下來起點的鄰居也可以標上暫時的答案了 因此1號點的答案可以暫時標上2 ![](https://i.imgur.com/11vvw0f.png =400x) 由於目前最近的點是1號點 因此可以用它來算出它的鄰居 ![](https://i.imgur.com/PRWffSc.png =400x) 現在最近的點是3號點 因此可以用它來算出它的鄰居 注意看5號點從7變成6囉 ![](https://i.imgur.com/K05mQ6V.png =500x) 一路算下去就可以得到答案了 ## <font color='darkblue'>站與路相連的世界 - 寫dijkstra的程式</font> 首先，先寫好一個struct來把「當前距離」以及「點的編號」綁起來 以便於放進priority_queue ```cpp= struct node { int number; int dis; bool operator<(const node& rhs) const { return dis<rhs.dis; } }; priority_queue<node, vector<node>, greater<node>> pq; ``` 再來，準備一個陣列代表每個點的答案 並且先把它們洗成超大數字 另外準備一個陣列代表每個點是不是已經變成紅色 並把他們都先設成否 ```cpp= int ans[100]; bool red[100]; for(int i=0;i<n;i++){ ans[i]=999999; red[i]=0; } ``` 接下來先搞定起點 ```cpp= ans[start_number]=0; node start={start_number, 0}; pq.push(start); ``` 接下來要不斷從priority_queue裡面拿新的數字出來 1.如果它已經是紅色了就跳過 2.把它變紅色 3.把它的鄰居都標上新答案(如果新答案比目前答案還要好的話啦) ```cpp= while(!pq.empty()) { node cur=pq.top(); pq.pop(); int num=cur.num; if(red[num]==1) continue; red[num]=1; for(int i=0;i<neighbor[num].size();i++) { int next_num=neighbor[num][i]; if(ans[next_num]>ans[num]+cost[num][i]){ ans[next_num]=ans[num]+cost[num][i]; node next={next_num, ans[next_num]}; pq.push(next); } } } ``` 最後再印出答案就好 也要記得檢查如果終點的答案是你當初設的999999 <font color='red'>代表起點走不到終點</font> 另外，999999真的夠大嗎? 難說，要看答案到底有可能多大 設定一個比可能的答案還要大的數字 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [B - Sending email ](https://vjudge.net/contest/276600#problem/B) > 有n台電腦，用m條網路線接在一起 > 每一條網路線都有特定的傳輸時間 > 給你n與m，以及起點和終點的編號 > 以及m行表示網路的兩端編號以及傳輸時間 > 請問最快傳到終點的時間是多少呢? > 如果走不到，也請印出unreachable 注意事項： 1.請用long long取代int 2.路是雙向通行，所以路的兩端都要存入鄰居資訊 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [C - Mice and Maze ](https://vjudge.net/contest/276600#problem/C) > 有N個老鼠洞，每個洞裡都有一隻老鼠 > 其中終點的編號為E > 以及有M條路 > 每條都告訴你從哪老鼠洞到哪個老鼠洞，以及那條路的長度 > 假設每隻老鼠都以最近的走法往終點跑，每秒可以向前跑一單位 > 請問T秒過後，有幾隻老鼠可以抵達終點? 注意事項： 1.路是單行道 2.最後一行不要印endl (題目要求) ## > 上一章：[BFS廣度優先搜尋](https://hackmd.io/s/BkxmExS8J4) > 下一章：[並查集 Disjoing set (Union find)](https://hackmd.io/s/rkRVS_o-4) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)