1. Dijkstra 演算法

2021-06-13 15:53:50 +0800 CST Tags: dijkstra, graph

問題：給定一張沒有負邊的帶權有向圖 (weighted directed graph) $G(V,E)$，請求出該圖從特定出發點 $s$ 走到其餘任意終點的最短距離。

解法：先說好我們的程序為回合制，並定義函數 $\delta: V\rightarrow \mathbb Z$ 裡的元素 $(v, \delta(v))$ 代表頂點 $v$ 對應到從 $s$ 走到 $v$ 的最短距離 (標準答案)，再定義函數 $\text{dist}: V\rightarrow \mathbb Z$ 裡的元素 $(v, \delta(v))$ 代表在計算過程中頂點 $v$ 對應到從 $s$ 走到 $v$ 的暫時最短距離 (計算過程)，那假設 $S_{i}\subseteq V$ 為第 $i$ 個回合開始之前的頂點集合，而且對於每個 $v\in S_i$ 的答案都早已穩定下來 $\text{dist}(v) = \delta(v)$，那麼在本回合我們將從 $V\setminus S_i$ 裡面每個至少從 Si 內的某個頂點踏一步出去就能抵達的頂點中挑出任一個離 $s$ 最近的頂點 $v_i := \mathop{\arg\min}\limits_{\substack{v\ \in\ V\setminus S_i,\\\exists u\ \in\ S_i\text{ s.t. }\\(u,v)\ \in\ E}}\{\min\limits_{\substack{u\ \in\ S_i,\\\exists (u,v)\ \in\ E}}\{\text{dist}(u)+w(u,v)\}\}$ 並且放鬆 (relax) 它此時的答案 $\text{dist}(v_i) := \min\limits_{\substack{u\ \in\ S_i,\\ \exists (u,v_i)\ \in\ E}}\{\text{dist}(u)+w(u,v_i)\}$，那根據下面的證明又能推得 $\text{dist}(v_i) = \delta(v_i)$，於是我們可以放心將 $v_i$ 加進 $S_{i+1} := S_i\cup\{v_i\}$ 並令為第 $i$ 個回合結束之後的頂點集合。只要一開始讓 $S_1:=\{s\}$ 而且 $\text{dist}(s):=0$，那麼重複上述步驟 $|V|-1$ 個回合之後就能得到每個頂點的標準答案。

證明：這邊我們想解釋在上述解法的第 $i$ 個回合的時候之所以能把點 $v_i$ 加進集合 $S_i$ 形成集合 $S_{i+1}$ 的理由，也就是 $\text{dist}(v_i) = \delta(v_i)$。用反證法來解釋就非常容易，如果存在一條從 $s$ 走到 $v_i$ 的無環最短路徑 $p$ 其最後一步是從 $S_i$ 以外的頂點走出來，而且它的距離又比我們原先以為的 $\min\limits_{\substack{u\ \in\ S_i,\\ \exists (u,v_i)\ \in\ E}}\{\text{dist}(u)+w(u,v_i)\}$ 還要來得短，那 $p$ 上必有一點 $v_o\notin S_i$ $(v_o\ne v_i)$ 使得 $\min\limits_{\substack{u\ \in\ S_i,\\ \exists (u,v_o)\ \in\ E}}\{\text{dist}(u)+w(u,v_o)\}$$< \min\limits_{\substack{u\ \in\ S_i,\\ \exists (u,v_i)\ \in\ E}}\{\text{dist}(u)+w(u,v_i)\}$，這麼一來就違反了我們當初的選點規則，因為此時應該優先選 $v_o$ 而非 $v_i$，於是原先猜想成立。即從 $s$ 走到 $v_i$ 的無環最短路徑之最後一步必定是從 $S_i$ 以內的頂點走出來，意即 $\delta(v_i) = \text{dist}(v_i) := \min\limits_{\substack{u\ \in\ S_i,\\ \exists (u,v_i)\ \in\ E}}\{\text{dist}(u)+w(u,v_i)\}$。

實作：假設在第 $i$ 個回合開始之前的候選頂點集合 $W_i\subseteq V\setminus S_i$ 確定滿足 $\forall w\in W_i,\ \exists u\in S_i$ such that $(u, w)\in E$，那麼該如何操作才能確保第 $i$ 個回合結束之後的候選頂點集合 $W_{i+1}\subseteq V\setminus S_{i+1}$ 使得 $\forall w\in W_{i+1},\ \exists u\in S_{i+1}$ such that $(u, w)\in E$？假設在本回合的 $S_{i+1} := S_i\cup\{v_i\}$，那麼其實讓 $W_{i+1} := \big(W_i \setminus \{v_i\}\big) \cup \big(N(v_i) \setminus S_i\big)$，其中 $N(v_i)$ 代表與 $v_i$ 相鄰的那些點，就能滿足指定條件。因為 $W_i \cap S_i = \emptyset$ 導致 $\big(W_i \setminus \{v_i\}\big) \cap \big(S_i\cup\{v_i\}\big) = \emptyset$，而 $N(v_i) \cap \{v_i\} = \emptyset$ 導致 $\big(N(v_i) \setminus S_i\big) \cap \big(\{v_i\}\cup S_i\big) = \emptyset$，所以根據分配律 $\Big(\big(W_i \setminus \{v_i\}\big) \cup \big(N(v_i) \setminus S_i\big)\Big) \cap (S_i\cup\{v_i\}) = \emptyset \cup \emptyset = \emptyset$，第一個條件 $W_{i+1} \cap S_{i+1} = \emptyset$ 成立。又因為 $\forall w\in W_i \setminus \{v_i\},$$\exists u\in S_i$ such that $(u, w)\in E$，而 $\forall w\in N(v_i) \setminus S_i,\ \exists u\in \{v_i\}$ such that $(u, w)\in E$，加上 $S_i$ 和 $\{v_i\}$ 都 $\subseteq S_{i+1}$，故第二個條件 $\forall w\in W_{i+1},\ \exists u\in S_{i+1}$ such that $(u, w)\in E$ 亦成立。換言之，我們可以毫不猶豫地把原先的 $v_i := \mathop{\arg\min}\limits_{\substack{v\ \in\ V\setminus S_i,\\\exists u\ \in\ S_i\text{ s.t. }\\(u,v)\ \in\ E}}\{…\}$ 取代為 $v_i:=$$\mathop{\arg\min}\limits_{v\ \in\ W_i}\{…\}$。只要初始集合 $W_1 := N(s)$ 即可。

那 $W_i$ 除了有縮小候選頂點範圍的功能之外，如果它還能馬上讓我們知道 $v_i$ 是誰，那是再好不過的。看到「馬上」和 “argmin” 兩詞彙，就會令人立刻聯想到 priority queue，而這個 $Q_i$ 就是用來實作 $W_i$ 的標準資料結構，它裡面的元素其實都是整數對 $(\text{dist}_i(v), v)$，因為 C++ 會優先比較第一個位置所以把距離擺前面。現在假設 $Q_i$ 恰好記錄 $W_i$ 裡每個頂點 $v$ 之從 $s$ 走到 $v$ 的路徑上的最後一步是由 $S_i$ 內的頂點走出來的最短距離 $\text{dist}_i(v)$，那我們想證明，從 $Q_i$ 取出 $(\text{dist}_i(v_i), v_i)$ 之後，如果只對於 $N(v_i)$ 裡滿足 $\text{dist}_i(v_i) + w(v_i, v) <$$\text{dist}_i(v)$ 的 $v$ 去更新它們的距離 $\text{dist}_{i+1}(v) := \text{dist}_i(v_i) + w(v_i, v)$ 並推進 $Q_i$，而在之前的回合已經存在 $Q_i$ 者用 decrease-key 操作代替 (以確保 $Q_i$ 不會包含重複的頂點資訊)，其餘 $Q_i$ 內的頂點 $v$ 保持不變 $\text{dist}_{i+1}(v) := \text{dist}_i(v)$，那經過此操作後形成的 $Q_{i+1}$ 必定剛好包含 $W_{i+1}$ 的頂點，而且它每個 $v$ 的 $\text{dist}_{i+1}(v)$ 就是從 $s$ 走到 $v$ 的路徑上最後一步是由 $S_{i+1}$ 內走出來的最短距離。回憶到 $W_{i+1}$$:= \big(W_i \setminus \{v_i\}\big) \cup \big(N(v_i) \setminus S_i\big)$，那麼 $W_i \setminus \{v_i\}$ 就相當於從 $Q_i$ 取出 $(\text{dist}_i(v_i), v_i)$，而 $\cup\ N(v_i)$ 就對應到只更新 $v_i$ 周圍的頂點 $v$ 們的資訊的意思，那為什麼只需要比較 $\text{dist}_i(v)$ 和 $\text{dist}_i(v_i) + w(v_i, v)$ 的大小？因為最後一步要從 $S_{i+1}$ 走出來這件事情剛好就能分成從 $S_i$ 走出來和從 $\{v_i\}$ 走出來兩部分，那又為什麼我們可以只推入從 $\{v_i\}$ 走出來會更近的那些頂點呢？因為 $S_i$ 內的 $\text{dist}_i(v) = \delta(v)$，它們不可能被更新到，於是 $\setminus S_i$ 獲得保證；事實上那些從 $S_i$ 走出來仍然保持比較近的頂點 $v$ 勢必早就都和 $S_i$ 相接，否則無法 $\text{dist}_i(v)$$< \infty$，而相接的意思就是 $v\in S_i\cup W_i$，若 $v\notin S_i$ 則 $v\in W_i$，這意味著 $(\text{dist}_i(v), v)$ 早就 $\in Q_i$，自然不推入也沒關係。初始值顯而易見應為 $Q_1 := \{\ (w(s, v), v)\ |\ v\in N(s)\ \}$。

上一段在更新距離資訊的時候有提到，如果某頂點 $v$ 已經存在於 $Q_i$ 裡的話，就改用 decrease-key 操作代替，目的是確保 $Q_i$ 不會包含重複的頂點資訊。如果使用的程式語言都不支援這種操作，那有沒有相對應的解決辦法？答案是有的，其實只要把新的元素照樣推進去，那原本舊的、距離比較大的元素基於 priority queue 的特性其優先度就會被排到後方，現在假設 $Q_i$ 包含兩個以上的同點資訊 $(f(v), v)$ 和 $(g(v), v)$，而且 $f(v) < g(v)$，那麼 $(f(v), v)$ 會優先被取出並更新周圍頂點資訊使得 $\forall u\in N(v)$ 更新後的 $d(u)\le f(v) + w(v,u)$，這樣的話下次取出 $(g(v), v)$ 的時候因為 $\forall u\in N(v)$ 都已經有 $d(u)\lt g(v) + w(v,u)$ 了，自然它對周遭的頂點都起不了更新的作用，周遭的頂點也就不可能再被它推進 queue，意思就是 $(g(v), v)$ 對演算法完全沒有作用，我們可以直接忽略，這樣就是 decrease-key 了。

總結：這個演算法主要利用從源頭開始擴張集合 $S$ 的方式，每次加一個距離 $S$ 最近的頂點進去就能保證新 $S$ 的頂點皆具標準答案。實作的一個難處是如何判斷與 $S$ 相鄰？從相鄰集合 $W$ 把最近點 $v$ 挑出來之後，只要再推入 $v$ 周圍的點 $N(v)$ 並排除掉 $S$，就能保持 $W$ 和 $S$ 的相鄰。另一個難處是要如何迅速的從 $W$ 挑出最近頂點，可以使用 priority queue 的方式，而且每個回合只要加入距離有變近的頂點即可。此外 priority queue 也不需要支援 decrease-key 的功能，因為每個從 queue 內取出來的頂點都只是為了要更新它周圍的頂點，同一個頂點只要出現第二次以後都不會對周圍頂點造成影響。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

typedef pair<int, int> pii;

int V=, s=; // V:=點數、s:=起始編號
int dist[V]; // 第 i 個頂點的最短距離為 dist[i]
pii adj[V]; // (v, w[u,v]) ∈ adj[u] for each edge (u,v)
priority_queue<pii, vector<pii>, greater<pii>> pq; // W_i

memset(dist, 0x7f, sizeof dist); // 每個點到 s 的距離初始化為無限大，除了下一行的
dist[s] = 0; // s 到 s 的距離為 0
pq.push(pii(dist[s], s)); // S_0 := ∅ 以及 W_0 := {s} (注意到這裡是從第 0 個回合開始，跟上面敘述從第 1 個回合開始有所不同)
while (!pq.empty()) { // S_i == V 的時候要停下來
    int vi = pq.top().second; pq.pop(); // W' := W_i \ {v_i} 以及 S_{i+1} := S_i ∪ {v_i}
    for (const auto &v: adj[vi]) // 檢視 v ∈ N(v_i) 是否有可以更新的距離
        if (dist[vi] + v.second < dist[v.first]) // 過濾掉 S_i 同時又不漏失必要的 N(v_i)
            dist[v.first] = dist[vi] + v.second, // 更新距離
            pq.push(pii(dist[v.first], v.first)); // W_{i+1} := W' ∪ (N(v_i) ∖ S_i)
}
for (int i=0; i<V; i++) // 印出 s 到每個頂點 i 的最短距離
    cout << i << ' ' << dist[i] << '\n';