Ch20 最短路徑 - DIJKSTRA

搭配 virtual judge解題系統

上一章：BFS廣度優先搜尋
下一章：並查集 Disjoing set (Union find)
回目錄：國立科學園區實驗中學C++程式語言自學講義

甚麼情況需要用到最短路徑

這是上一單元的圖
從藍色走到紅色最快的走法
也就是走最少格子的走法
我們在上一章學會用BFS來解決

那麼這章
我們來讓題目變得更複雜：
每一格都有「過路費」
你要找的不是「經過最少格子的走法」
而是「需要付最少過路費的走法」

如圖，每一格上面的數字代表的是那格的過路費
這題的正解為灰色那條路
代表的是過路費最低的走法

同樣都是能走的路
我們必須選擇過路費較低的格子走
甚至也有可能出現要「繞路」比較划算的情況

在這個案例中
儘管它好像繞了遠路、走了較多格子
但以下這走法是最划算的

那麼究竟怎麼在給定的題目中
找到花最少錢的走法呢?
這就是這一章要教的
「最短路徑演算法」

最短路徑演算法-dijkstra

用來解決這種問題的演算法有很多流派
各有各的長處

有的可以拿來算出所有點兩兩之間的最短距離
有的專門拿來算特定起點到每一點的最短距離；
有的不能處理路徑長為負數的案例
有的可以處理負數路徑還能順便偵測負環

這一章要介紹的是dijkstra演算法
因為它和BFS很像
不要問我dijkstra怎麼念
我都念dijkstra

接下來示範如何用dijkstra演算法
逐一算出從起點走到每一格所需要的最小花費

首先
到達左下角格子所需要的最小花費是4
這點是肯定的
因為它就是起點了
沒有其他走法可以有更小的花費了
我們用紅色來代表已經肯定的答案

接下來
起點的上方與右邊的「暫時答案」都可以從起點的答案推出來
為何說是「暫時」呢
因為還有可能有繞遠路的走法來讓答案更小
因此先用綠色代表「我暫時發現這格目前的答案是5」、「我暫時發現這格目前的答案是13」

接下來
我們要在所有的綠色裡面
選一個最小的值
把他變成「肯定的紅色」

因此它已經是目前已知的最近格子了
已經不可能透過繞遠路來讓它變得更近
(↑這概念不好懂，但是是核心觀念哦，有問題請盡量質疑！而且這只適用於「沒有負的過路費」的情況！)

把左上方的5變成「肯定的答案」的同時
要順便透過它來找出它上下左右的答案
這時我們算出他右邊的答案是7

再來一樣是從所有綠色的格子裡面選數字最小的那個變成紅色
再把它的上下左右格子也找出答案

一直這樣標下去
直到終點的格子也變成紅色
就可以確定答案了

問題來了
剛才每次都在所有的綠格子中找數字最小的
可是要怎麼最有效率地找呢?
把所有格子都看過一遍找最小的一定會超時
希望有個神奇袋子可以每次都把最小的數字浮上來給我

甚麼樣的袋子可以做到這樣的事情呢?

dijkstra的好朋友 - priority queue

上上個單元在教stack與queue的時候
最後面有順便講到priority queue

priority queue的行為是這樣的
你把一堆數字丟進去
他會把最大的數字放在它的頂端

當你把一個數字pop掉時
它會自動調整裡面剩下的數字
把剩的裡面最大的移到頂端

當你把新數字丟進去時
它也會自動把新數字喬到它該去的位置

不過在這個題目中
我們有一些特別的要求

1. 希望每次拿到的是最小的數字
2. 希望這個數字能夠跟它格子的座標綁在一起放在袋子裡

首先先介紹怎麼把資料給綁在一起
上次是使用pair
這次介紹「struct」
不過基本上用途是類似的

struct相當一個盒子
你要把這個盒子取一個名稱
在這裡我把它取名為"cell"

記得把它宣告在main的外面

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裡面的資料

cout<<A.r<<endl;   //印出0
cout<<C.dis<<endl; //印出3
int q = B.c;       //q變為2

有了這樣的盒子
我們就可以把座標和它的答案綁起來了

最後一步是要能把這盒子放進priority_queue裡面
並且要求它「把dis最小的放最上面」

想要讓它把dis最小的放最上面
我們需要在宣告struct cell的時候加上這一段

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 的時候
我們需要宣告成：

priority_queue<cell, vector<cell>, greater<cell> > pq;

這樣一來可以示範整段prioiry_queue的用法了

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怎麼使用後
可以來看看整個程式碼了

寫dijkstra的程式

一開始先把每一格的答案都先洗成999999999
(一定要夠大，但也不能超過int的範圍)
這樣一來就可以在每次找到更近的路時取代舊答案
也順便把每一格都標上「不是紅色」

for(int i=0;i<1000;i++){
    for(int j=0;j<1000;j++){
        ans[i][j]=999999999;
        red[i][j]=0;
    }
}

首先，起點可以先標上答案了
起點的答案就是起點那格的花費
並且把起點的座標與答案綁在一起
丟進priority_queue裡

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.如果新答案比目前答案還要好的話，把它的上下左右都標上新答案

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);
            }
        }
    }
}

最後只要印出終點那格的答案就好了~

【學生練習題】

• A - Number Maze

站與路相連的世界

上一章的BFS
與剛才的例子
都是在格子世界中發生的
然而這世界哪有這種格子結構呢
反而像是鐵路、飛機
大多都是「站與路」的結構
因此接下來要介紹「站與路」的結構要怎麼算出最短路徑

如圖就是站與路的結構
我們稱之為「Graph」(圖)
其中點與點之間可能會有路相接

現在假設每條路都有自己的過路費
我們用綠色的數字代表那條路的過路費

題目可能會說是過路費
也可能會說是通過這條路所要花掉的時間
總之都是「花費成本」的概念，我們用「cost」來代稱

為了表達方便，我們通常會在每個點加上編號

這樣一來可以出很多問題
以這章來舉例的話
可以問你「0號點至4號點的最短距離是多少呢?」

站與路相連的世界 - 資料結構

為了表達一張圖
題目會告訴你總共有幾個點、幾條路
並且給你每一條路的資訊：
它是連接哪兩個點，以及它的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就有多大

伸縮陣列 - vector

首先介紹vector如何使用
假設你的vector是拿來存int的
並且取名為vv
你可以宣告成

#include<vector>

vector<int> vv;

現在這個vv的size是0
你可以塞東西進去了
你塞幾個他的size就是多少

vv.push_back(3);
vv.push_back(4);
vv.push_back(1);

這時他的size就是3了
可以像取陣列的值一樣把裡面的東西都拿出來看

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」

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);
}

你可以隨意印東西出來看看

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;
}

站與路相連的世界 - 找出最短路徑

起點是0號
請問起點至4號點的最短距離為多少呢?
這一樣可以使用dijkstra來解決

首先，起點的距離為0，肯定的

接下來起點的鄰居也可以標上暫時的答案了
因此1號點的答案可以暫時標上2

由於目前最近的點是1號點
因此可以用它來算出它的鄰居

現在最近的點是3號點
因此可以用它來算出它的鄰居
注意看5號點從7變成6囉

一路算下去就可以得到答案了

站與路相連的世界 - 寫dijkstra的程式

首先，先寫好一個struct來把「當前距離」以及「點的編號」綁起來
以便於放進priority_queue

struct node
{
    int number;
    int dis;
    bool operator<(const node& rhs) const
    {
        return dis<rhs.dis;
    }
};

priority_queue<node, vector<node>, greater<node>> pq;

再來，準備一個陣列代表每個點的答案
並且先把它們洗成超大數字
另外準備一個陣列代表每個點是不是已經變成紅色
並把他們都先設成否

int ans[100];
bool red[100];

for(int i=0;i<n;i++){
    ans[i]=999999;
    red[i]=0;
}

接下來先搞定起點

ans[start_number]=0;
node start={start_number, 0};
pq.push(start);

接下來要不斷從priority_queue裡面拿新的數字出來
1.如果它已經是紅色了就跳過
2.把它變紅色
3.把它的鄰居都標上新答案(如果新答案比目前答案還要好的話啦)

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
代表起點走不到終點

另外，999999真的夠大嗎?
難說，要看答案到底有可能多大
設定一個比可能的答案還要大的數字

【學生練習題】

• B - Sending email
  有n台電腦，用m條網路線接在一起
  每一條網路線都有特定的傳輸時間
  給你n與m，以及起點和終點的編號
  以及m行表示網路的兩端編號以及傳輸時間
  請問最快傳到終點的時間是多少呢?
  如果走不到，也請印出unreachable

注意事項：
1.請用long long取代int
2.路是雙向通行，所以路的兩端都要存入鄰居資訊

【學生練習題】

• C - Mice and Maze
  有N個老鼠洞，每個洞裡都有一隻老鼠
  其中終點的編號為E
  以及有M條路
  每條都告訴你從哪老鼠洞到哪個老鼠洞，以及那條路的長度
  假設每隻老鼠都以最近的走法往終點跑，每秒可以向前跑一單位
  請問T秒過後，有幾隻老鼠可以抵達終點?

注意事項：
1.路是單行道
2.最後一行不要印endl (題目要求)

上一章：BFS廣度優先搜尋
下一章：並查集 Disjoing set (Union find)
回目錄：國立科學園區實驗中學C++程式語言自學講義