# 第十三週課程內容 (2018/11/23)
這週同樣是圖論，會以經典的最短路徑問題為主。
# 最短路徑 Shortest Path
最短路徑問題主要求從一個點走到另一個點中，所有的路徑裡面，長度最短是多少。
它的應用相當廣泛，從走迷宮、自動尋徑到導航、甚至最小步驟、最小花費最佳解等。
## 邊的權重有無 Weighted && Unweighted
之前討論的 graph 每條邊並沒有權重（長度）的概念，
最短路徑就只需要討論走過最少幾條邊，可以用 BFS 求得。
這使用在「每一步花費相同」的情況下，像走迷宮往上下左右走一步，花費相同的時間。
但考慮以下題目：
> 在一個 n\*m 大小的迷宮中，給你起點和終點、以及障礙物的位置，
> 有些地方可能有上鎖的門，告訴你每一道門需要花費多少單位時間開鎖，
> 每走一格花費一單位時間，問從起點到終點最少需要多少單位時間？
開鎖這件事讓通過「門」的格子所花費的時間，和其他格子不相同。
這會讓 BFS 變得不適用，因為你再也無法保證 queue 的花費時間呈不遞減的性質，
也就無法保證首次走到一個格子上時，就是最小花費時間。
儘管我們可以將花費 k 單位時間來開鎖的門，拆解成 k 個格子，
來維持每步花費相同時間的性質，如下圖為 k = 3 的拆解例子：
透過將「門」拆成三個點，從外面進來必定走到第一個點，
要出去必須先走到第三個點，來維持「在這一格上面花 k 單位時間才出得去」這件事，
同時維持每一步花 1 單位時間的性質，來保證 queue 花費時間呈不遞減狀態。
實際上，把點看成每一個交叉路口（或者死胡同），把每條邊看成連接它們的道路，
那麼每條道路可能是不一樣長的，而且不見得是直線距離，中間可以彎曲。
於是我們對每條邊額外加上一個「權重」的資訊，「權重」的意義會隨著題目改變，
可能是長度、距離，或者花費，等等。
最短路徑問題便從「路徑上經過的邊最少」變成了「路徑上經過的邊的權重總和最小」。
而 BFS 僅適用於「每條路徑的權重皆相同」的前提下。
## 單端最短路徑 Single-Source Shortest-Path
實際上，並不存在單求「兩點間」最短路徑的做法。
「兩點間」的最短路徑，通常會依賴於「起點到其他點」的最短路徑，
也就是說，假設從起點 S 要走到終點 T，其最短路徑經過點 K，
那麼 S → K → T 依賴於 S → K 的最短路徑，以及 K → T 的最短路徑。
若 S → K 並非是最短路徑，則必定可以找到更短的路徑，以縮短 S → K 的距離，
則整體 S → K → T 的距離會跟著被縮短，表示一開始的 S → K → T 並非最短路徑。
因此，通常會求「起點到所有點」的最短路徑，再從中找出「起點到終點」的最短路徑。
## Dijkstra
Dijkstra 的概念是：從起點出發，列出所有能夠到達的點，
先挑最短的那個一定不會比先挑其他點更差。
假如今天有 3 個能夠到達的點 A、B、C，距離分別是 2、4、7，
最短的是走到 A，那麼選擇先走到 A 一定不會更糟。
S → A → B 有可能比 4 短，S → A → C 有可能比 C 短，
但是反過來 S → B → A 光是走到 B 的距離就比 S 直接到 A 來得遠，
S → C → A 也是同理。
所以先選距離遠的，有可能之後被推翻；先選距離短的，則不可能出現其它路徑比它更短，
因為其它路徑光路上必須經過其他點，就已經更遠了。
也就是說，「目前能到達的點」中，「距離最短」的那個點，其目前離起點的距離，
就是「起點走到它的最短距離」。
光是先走到其他點就更遠了，不可能有其他路徑能縮短這個距離。
因此，Dijkstra 的做法如下：
- 一開始從起點列出所有「能夠到達的點」
- 每次找出「最近的」能夠到達的點，則此時可確定起點到這個點的最短距離
- 看看能否經過這個點走到其他「未能到達的點」，或者讓「已能到達的點」距離縮短
- 把這個點拔掉，反覆再找下一個「最近的」能夠到達的點
```cpp=
// 將起點 S 目前距離所有點距離初始化為 -1 表示還未能到達
// 有些人喜歡把距離設為「無窮大」，但實際上整數不可能 assign 成「無窮大」
// 最多就是 int 或 long long 的極大值，如果不夠大反而容易死得不明不白
// 另一個好處是 -1 可以 memset()
for (int i=0; i<V; i++)
{
dis[i] = -1;
}
// 一開始起點離自己距離是 0
dis[S] = 0;
// 反覆尋找目前距離最短的點，則可確定起點與它的最短距離
// 總共 V 個點所以跑 V 次（含起點自身）
for (int i=0; i<V; i++)
{
// 找到距離最短、且未確定最短距離的點，放到 cur
int cur = -1;
for (int j=0; j<V; j++)
{
// !used[j] 代表未確定最短距離；dis[j] >= 0 代表目前已走得到
if (!used[j] && dis[j] >= 0)
{
// 如果還未找到任何點，或比目前找到的點距離更短，就更新 cur
if (cur == -1 || dis[j] < dis[cur])
{
cur = j;
}
}
}
// 如果 cur 未被更新，表示找不到任何可到達點，此 graph 不連通
if (cur < 0)
{
break;
}
// 設為此點已確定最短距離
used[cur] = true;
// 更新所有 cur 走得到的點
for (int j=0; j<adj[cur].size(); j++)
{
int nxt = adj[cur][j].id;
// 僅更新未確定最短距離的點
if (!used[nxt])
{
int d = adj[cur][j].dis;
// 若未能到達，或已能到達但距離大於起點先到 cur 再到 nxt 就更新距離
if (dis[nxt] < 0 || dis[cur] + d < dis[nxt])
{
dis[nxt] = dis[cur] + d;
}
}
}
}
if (dis[T] < 0)
{
cout << "Impossible to reach.\n";
}
else
{
cout << dis[T] << '\n';
}
```
每次找出最短距離的點，複雜度為 V，這件事共要做 V 次，是 V^2^。
更新的部份每個點最多更新一次，每次只更新相鄰的點，
相當於每條邊被更新到兩次，因此更新部份複雜度為 E。
可看出 Dijkstra 複雜度為 V^2^ + E。
### Dijkstra with heap
從複雜度可看出瓶頸主要在 V^2^，而 E 則是更新距離時逃不掉的必要最小花費。
每次尋找極值可想到使用 heap 壓至 lg V，則理論上整體可降至 V lg V + E。
由於距離更新可能打壞整個 heap 的結構，於是改為每次傳入距離，
更新時將新的距離作為新的點塞進 heap。
```cpp=
// 一開始將起點塞進 heap
heap[0].id = S;
heap[0].dis = 0;
hn = 1;
push_heap(heap, heap+hn, comp);
dis[S] = 0;
for (int i=0; i<V; i++)
{
// 找到距離最短、且未確定最短距離的點，放到 cur
int cur = -1;
// 由於點在更新距離時是重覆塞到 heap 的，所以應反覆至找到未確定最短距離的點
while (hn > 0)
{
int nxt = heap[0].id;
pop_heap(heap, heap+hn, comp);
hn--;
if (!used[nxt])
{
cur = nxt;
break;
}
}
// 如果 cur 未被更新，表示找不到任何可到達點，此 graph 不連通
if (cur < 0)
{
break;
}
// 設為此點已確定最短距離
used[cur] = true;
// 更新所有 cur 走得到的點
for (int j=0; j<adj[cur].size(); j++)
{
int nxt = adj[cur][j].id;
// 僅更新未確定最短距離的點
if (!used[nxt])
{
int d = adj[cur][j].dis;
// 若未能到達，或已能到達但距離大於起點先到 cur 再到 nxt 就更新距離
if (dis[nxt] < 0 || dis[cur] + d < dis[nxt])
{
dis[nxt] = dis[cur] + d;
// 更新時將距離連同點編號塞進 heap 以免參照 dis[nxt] 破壞結構
heap[hn].id = nxt;
heap[hn].dis = dis[nxt];
hn++;
push_heap(heap, heap+hn, comp);
}
}
}
}
if (dis[T] < 0)
{
cout << "Impossible to reach.\n";
}
else
{
cout << dis[T] << '\n';
}
```
### BFS with Priority-queue？BFS v.s. Dijkstra
Dijkstra 大致步驟是：
- 從 heap (priority queue) 拉出距離最短的點
- 確定該點離起點的最短距離
- 更新所有相鄰點的最短距離
回想一下 BFS：
- 從 queue 拉出下一個點（滿足目前距離最短的條件）
- 確定該點離起點的最短距離
- 更新所有相鄰的點
就會發現其實這兩個方法幾乎一樣，BFS 就和把 Dijkstra 用在無權重邊時幾乎相同。
某方面來說 Dijkstra 就只是把 BFS 的 queue 換成 heap (priority queue)，
而 BFS 只是 Dijkstra 在無權重邊下的一種特例。
## 負邊 Negative Edge
Dijkstra 的前提在某個特殊情形下是不正確的：
> 當存在兩個點 p, q 且 S → p < S → q
> 可是 S → q → p 卻比 S → p 更短時
換句話說，存在一個 q → p 使得
> S → p < S → q
> S → q + q → p < S → p
整理可知：
> S → q + q → p < S → p < S → q
> => S → q + q → p < S → q
> => q → p < 0
也就是說，當存在「邊的權重為負數」的情況時，Dijkstra 的假設前提就會是錯的，
導致 Dijkstra 無法計算出正確的最短路徑。
## 負環 Negative Cycle
一個更糟的情況是：存在一個負環，繞此環一圈的權重總和是負的。
這會使得最短路徑不存在；只要一踏進負環，那麼再多繞一圈永遠是更好的。
離開負環走向終點就輸了的概念。
## Bellman Ford
Bellman-Ford 雖然複雜度高於 Dijkstra 但能夠應用在負邊上。
它的理念很簡單：
> 窮舉每一條邊，看是否有哪一條邊會讓他的兩端點離起點更近。
在不考慮負環的前提下，最短路徑最多也只會走過 V-1 條邊，
這會將所有點都踩過一次。
每次的窮舉，都應該能讓我們最少找到一條在最短路徑上的邊，並更新掉其中一個端點。
因此，「窮舉每一條邊」這個動作，最糟的情形也只要做 V-1 次之後，就能找到最短路徑。
反過來說，如果將「窮舉每一條邊」這個動作做超過 V-1 次，
發現仍有邊能夠更新到其兩端點離 S 的最短距離時，
表示此 graph 應該有負環的存在，否則在 V-1 次後應收斂至無法再更新任何點。
```cpp=
// 由於對應負邊，距離可能為負，就只能設個很大的數當作無窮大來用了
for (int i=0; i<V; i++)
{
dis[i] = INF;
}
dis[S] = 0;
// 窮舉 V-1 次的所有邊
for (int k=1; k<V; k++)
{
// 不需按順序窮舉所有邊時，邊集合較方便
for (int i=0; i<edge_list.size(); i++)
{
// 預先用變數暫存，寫起來會方便許多
int p = edge_list[i].p;
int q = edge_list[i].q;
int d = edge_list[i].weight;
// 注意：更新時若 INF 太接近變數儲存上限，INF + d 很可能溢位
// 拿 p 更新 q
if (dis[p] + d < dis[q])
{
dis[q] = dis[p] + d;
}
// 拿 q 更新 p
if (dis[q] + d < dis[p])
{
dis[p] = dis[q] + d;
}
}
}
// dis[T] 會存著 S 到 T 的最短距離
// 再窮舉一次所有邊，如果還能更新就表示存在負環
```
複雜度為 V-1 次的窮舉所有邊，故為 VE。
## 多端最短路徑 Multi-Source Shortest-Path
多端最短路徑即是求 graph 上任意起點對所有點的最短路徑，
這樣對任意兩個點都可知道他們之間的最短路徑。
暴力解可以對所有點都求一次單端的最短路徑，
相當於做 V 次的 Dijkstra，
複雜度為 V^3^ + VE 或者 V^2^ lg V + VE。
## Floyd Warshall
著名的非常好記，卻非常難理解、以及證明的演算法。
可以先記下，遇到最短路徑問題總之先用用看再說。
```cpp=
// 為求任意點到任意點，鄰接矩陣會是較合適的選項
// 窮舉每一個點為中繼點
for (int k=0; k<V; k++)
{
// 對每個中繼點 k 檢查所有點對 (i, j) 看經過 k 是否會更短
// 此時的 (i, j) 實際意義上為：
// 從 i 出發，以任意順序走過 0 ~ k-1 中，任意個數的點後
// 到達 j 的最短路徑距離為多少
// 在迴圈結束時，從 0 ~ k-1 被更新為 0 ~ k
for (int i=0; i<V; i++)
{
for (int j=0; j<V; j++)
{
if (dis[i][k] + dis[k][j] < dis[i][j])
{
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
```
注意 k 一定要在最外層，窮舉每個點 k 作為中繼點，
看 i 先到 k 再到 j 是否比目前已知 i 到 j 的最短距離要來得更短。
重要的概念和之前一樣：只要一條路徑 S → T 為 S 到 T 的最短路徑，
那麼這條路徑上任取兩個點 P, Q 則此路徑上的 P → Q 也是 P 到 Q 的最短路徑。
假設兩點 1 → 2 之間的最短路徑是 1, 5, 3, 8, 6, 2 的順序，
任取兩點如 5, 8 可知 5 → 8 最短路徑為 5, 3, 8；
如 3, 2 可知 3 → 2 的最短路徑為 3, 8, 6, 2。
證明方式和上面相同，如果 3, 2 的最短路徑不是 3, 8, 6, 2
那把這條路徑中的 3, 8, 6, 2 換成 3, 2 的最短路徑，
3, 2 的最短路徑一定比非最短路徑的 3, 8, 6, 2 來得更短，
置換後比 1, 5, 3, 8, 6, 2 更短，
和「1, 5, 3, 8, 6, 2 是 1 → 2 的最短路徑」矛盾。
而這條最短路在 k = 8 時被找出，由 1, 8 和 8, 2 組成；
而 1, 8 的最短路徑在 k = 5 時被找出，由 1, 5 和 5, 8 組成；
1, 5 一開始就相鄰，而 5, 8 在 k = 3 時被找出；
8, 2 在 k = 6 時被找出，…依此類推。
由類似的方法遞迴去看，可證明不論最短路徑途經哪些點，
在窮舉以 k 為中繼點的過程，都必定能夠被找出。
# 最小生成樹 Minimum Spanning Tree（MST）
考慮以下問題：
> 有 N 個城市彼此互不相連，告訴你每個城市間建造道路的花費，
> 問如何建立道路，才能使所有城市相連，並且總花費要最小？
> 任兩城市間，可透過其他城市往來，就算相連。
這種題目就是標準的最小生成樹問題：
取一些邊使得整個 graph 連通，讓這些邊的權重總和最小。
不過你可能會想：這跟樹有什麼關聯？
有的，只是圖論的樹和前面講的樹不太相同。
## 樹 Tree
在圖論上，一個互相連通、但沒有環的 graph 稱為樹。
從互相連通可知邊的個數至少是 V-1，
每一條邊可以把兩個互不連通的連通塊連起來，
而一開始 V 個點互不相連時，共有 V 個連通塊，需要 V-1 條邊才能連通。
又在 V-1 條邊且連通的 graph 上，不管在哪邊再追加一條新的邊，
都相當於是在連通塊中追加一條新的邊進來。
連通塊間已經相通了，再多一條邊連通，就一定會形成環。
因此，一個有 V 個點的樹，一定恰有 V-1 條邊。
若要用盡量小的花費連結起整個 graph 那肯定不會讓兩個連通塊間再追加邊，
這只會增加花費，而不會促進整個 graph 的連通。
那麼最後，最小生成樹問題做出來的解肯定是以最小限度的邊連通整個 graph，
就肯定是樹了。
## Prim
剛學過 Dijkstra 可能會聯想到：Dijkstra 不就是從起點開始，
在加入一個又一個的點後，慢慢把原本走不到的點變成走得到、慢慢找出最短路嗎？
Prim 就是個類似的概念：從某個點出發，把連得到的點加進來，使其和起點連通，
如此一步步將新的點拉進來，壯大起點所在的連通塊，
直到將所有點加進來，就會形成一顆樹了。
和 Dijkstra 不同的地方在，Dijkstra 是保存和起點的距離，
而 Prim 則是保存和起點所在連通塊達成連通的最小花費。
因此 Prim 的概念其實不重視起點，而是在「連通塊」上。
同樣地，每次找出和連通塊相連花費最小的點，可能可以更新和其他點的花費；
可是其他點先拉進來不可能更新花費最小的點的花費，光是加進來就讓花費更高了。
因此，每次將花費最便宜的點拉進連通塊，再更新連通塊和所有點相連的花費，
直到將所有點加進連通塊中，就形成了最小生成樹。
code 和 Dijkstra 可以說幾乎完全相同，
除了 dis 的更新不是用路徑長，而是與連通塊相連的花費。
原本的 code 用註解方式留著做對比，就不難發現有多像。
有改動的地方才有註解。
```cpp=
// 追加的部份：計算最終花費用
int ans = 0;
for (int i=0; i<V; i++)
{
dis[i] = -1;
}
dis[S] = 0;
for (int i=0; i<V; i++)
{
int cur = -1;
for (int j=0; j<V; j++)
{
if (!used[j] && dis[j] >= 0)
{
if (cur == -1 || dis[j] < dis[cur])
{
cur = j;
}
}
}
if (cur < 0)
{
break;
}
// 追加的部份：計算最終花費
ans += dis[cur];
used[cur] = true;
for (int j=0; j<adj[cur].size(); j++)
{
int nxt = adj[cur][j].id;
if (!used[nxt])
{
int d = adj[cur][j].dis;
// 這裡改成更新「和連通塊（上的任何一個點）相連所需最小花費」
// if (dis[nxt] < 0 || dis[cur] + d < dis[nxt])
if (dis[nxt] < 0 || d < dis[nxt])
{
// dis[nxt] = dis[cur] + d;
dis[nxt] = d;
}
}
}
}
if (dis[T] < 0)
{
cout << "Impossible to reach.\n";
}
else
{
// 這裡改成輸出 ans
// cout << dis[T] << '\n';
cout << ans << '\n';
}
```
複雜度也完全相同，V^2^ + E。
同樣能用 heap 優化，由於和 Dijkstra 實在太過相似，heap 版就略過不提。
## Kruskal
相對於 Prim 從點和連通塊的方向出發，
Kruskal 則是從邊的選擇開始。
從花費最小的邊選起，如果目前這條邊，能夠將不連通的兩個連通塊合併，
那麼就用它合併；否則就忽略。
這方法保證了先找到的邊一定是花費更小的，
後來再找到的邊如果兩端已處在同一個連通塊，
那表示這個連通塊可以只用比後來的邊花費更小的邊來連通。
放上去後形成的環，不管打掉那一條邊，都只會更貴，所以一定不會讓結果更好。
這方法需要能夠很快速地問到一條邊的兩端點，它們是不是位於同一個連通塊中。
以及很快速地合併兩個連通塊。Disjoing set 可以很漂亮地達成這兩個要求。
```cpp=
// 先對邊集合按花費排序
sort(edge_list.begin(), edge_list.end(), comp);
// 記錄採用的邊的花費總和，以及已採用邊的數量
// 數量用來判斷此圖是否不可能連通（無解），或者提早結束用
int ans = 0;
int count = 0;
// 由花費小到大窮舉每一條邊
// 由樹的定義只要採用 V-1 條邊即可連通，也無須再多；
// 因此條件追加一條：「當採用的邊未滿 V-1 條」即繼續窮舉
for (int i=0; i<edge_list.size()&&count<V-1; i++)
{
// 尋找老大，用以判定是否已處於同個連通塊
int p = find_root(edge_list[i].p);
int q = find_root(edge_list[i].q);
// 若老大不同，表示不在同個連通塊，就採用這條邊將它們連起來
if (p != q)
{
// 將 p 和 q 拉到同一個連通塊，記錄採用邊的花費
parent[p] = q;
ans += edge_list[i].cost;
count++;
}
}
// 若未能採用滿 V-1 條邊，表示此 graph 無解，就算加入所有邊也無法連通
if (count != V-1)
{
cout << "Not reachable.\n";
}
// 若有解則輸出最小花費總和 ans
else
{
cout << ans << '\n';
}
```
# 重邊與自連邊
最後就是提醒一下，圖論題必須小心是否存在以下幾種狀況：
- 整個 graph 不連通，或無法連通
- 重邊（兩點間可以擁有超過一條邊）
- 自連邊（邊的兩端連到同一個點）
# 作業
基本上是最短路徑和 MST。
[SkyOJ 連結](http://sky.tfcis.org/rank.php?mod=commonboard&id=84)
- UVa523
- UVa534
- UVa558
- UVa908
- UVa10048
- UVa10147
- UVa10801
- UVa10986
## 給資訊社競賽組的作業
:::warning
非資訊社競賽組的同學們可以無視這部份。
當然也歡迎挑戰，雖然可能會十分吃力，
並且可能會需要你們完全沒學過的技能與知識。
:::
同樣不定型
[SkyOJ 連結](http://sky.tfcis.org/rank.php?mod=commonboard&id=85)
- UVa613
- UVa833
- UVa869
- UVa10380
- UVa10532
- UVa11341
- UVa11374
- UVa11386
- UVa11402
- UVa11492
###### tags: `APCS2018上`
Sign in with Wallet
Connect another wallet