完整解析 Dijkstra’s Algorithm，內涵推導&證明讓你輕鬆讀懂 Dijkstra

前言

給定一個graph $G = (V, E)$，其中 $V$ 為圖中所有點，$E$ 為點和點的連接權重，今定義起始點 $s \in V$ 和終點 $t \in V$，請問要如何找出從 $s$ 到 $t$ 的最短路徑？使用 greedy 方式搜尋是行不通的，因為若每次在抉擇路徑的時候皆選擇最短路徑，最終某個時間點可能會出現非常遠的路徑但是又不得不選擇該路徑，因為每次選擇路徑時我們只看 “local” 的話必定會忽略全局最佳的路徑，因此 Dijkstra’s algorithm 在此登場，為了幫助我們搜尋最短路徑。在正式開始之前我們先定義幾個將會用到的變數：

Dijkstra’s Algorithm

這裡直接展示 Dijkstras’s algorithm 的步驟:
$$
\begin{aligned}
&\textbf{Init: } \mathbf{S} = \{\}, \pi(s) = 0, \pi(v) = \infty, \forall v \in V – \{s\} \\
&\textbf{Repeat: } \\
&\hspace{1cm} u = \arg \min_{v \in V-S} \pi (v) \\
&\hspace{1cm} \mathbf{S} = \mathbf{S} \bigcup \{u\} \\
&\hspace{1cm} \text{find } u \text{‘s neighbors: } v_i, \forall l(u, v_i) \neq \infty \\
&\hspace{1cm} \pi (v_i) = \min (\pi (v_i), \pi (u) + l(u, v_i)) = \min (\pi (v_i), d(u) + l(u, v_i)) \\
&\textbf{until } \mathbf{S} = V
\end{aligned}
$$

最初我們將 $\pi(s)$ 設為 $0$，其它 $pi(v) = \infty, \forall v \in V – \mathbf{S}$，這點可以很直觀的理解因為從 $s$ 到 $s$ 所需的距離必定為 0，而事實上 $s$ 到 $s$ 的最短路徑 $d(s)$ 也為 0。

接下來我們從未被找到最短距離的集合中 $V – \mathbf{S}$ 找尋擁有最小距離的點：$$
u = \arg \min_{v \in V-S} \pi (v)
$$ 並將此點視為已找到最短距離，加入 $\mathbf{S}$ 集合中。在第一次迭代過程中，我們可以發現 $u$ 就是 $s$ 這個點，並且如上述，我們已知 $\pi(s) = d(s) = 0$，因此可以放心將 $s$ 加入 $\mathbf{S}$，在第二次的迭代中，我們將會利用歸納法(induction)證明透過此演算法找到的點皆是最佳路徑。

最後我們更新與 $u$ 有聯結的 $v_i$ 之距離 $\pi(v_i)$，從 $s$ 至 $v_i$ 的最短距離可能為原本已經紀錄在 $\pi(v_i)$ 的值，也有可能是從 $s$ 到 $u$ 再到 $v_i$ 的距離 $s \rightarrow u \rightarrow v_i$，但也有可能兩者都不是，無論如何我們可以先將較小的距離紀錄下來以此距離更新：$$
\pi (v_i) = \min (\pi (v_i), \pi (u) + l(u, v_i)) = \min (\pi (v_i), d(u) + l(u, v_i))
$$

至此 Dijkstra’s algorithm 的一個 iteration 已經描述完畢，接下來只要重覆上述動作直到所有的點都加入到 $\mathbf{S}$ 集合中 ($\mathbf{S} = V$)，即代表完成搜索。

推導

學習 Dijkstra’s algorithm 時，都會有一個疑問，就是如何確定 $u = \arg \min_{v \in V-S} \pi (v)$ 一定代表找到最短路徑的點？有沒有可能有其它路徑我們沒有考慮到，但是反而是最短的？這個問題的答案是否定的，用 $u = \arg \min_{v \in V-S} \pi (v)$ 所找到的點，必定已經找到最短路徑。

我們可以用歸納法證明，證明起始時符合條件，且當 $\mathbf{S}$ 中的點 $u_1, …, u_n$ 符合條件，下一步加入的點 $u_{n+1}$ 也會符合條件後，我們就可以確保依照此演算法執行到最後皆可以符合最短距離的要求。

首先當 $\mathbf{S} = \{\}$ 時，我們可以明確知道上述論點必定正確，因為 $\pi (s) = 0$ 必定為最小值。接下來假設所有 $\mathbf{S}$ 中的點 $u_1, …, u_n$ 皆找到最短距離 $\pi(u) = d(u), \forall u \in \mathbf{S}$ ，那我們要證明 $u_{n+1} = \arg \min_{v \in V-S} \pi (v)$ 也是最短距離。

假設目前 $\mathbf{S}$ 中找到 $u_1, …, u_n$ 的最短距離，且接下來找到 $u_{n+1} = \arg \min_{v \in V-S} \pi (v)$，那依照論述 $\pi(u_{n+1})$ 也已經是最短距離了。如果有另一條路徑 $P$ (非 $\pi(u_{n+1})$ 的路徑) 也可以從 $s$ 抵達 $u_{n+1}$，該路徑必定會有一個 $u_i$ 為最後要離開 $\mathbf{S}$ 的點 ($u_i$ 也可以為 $s$ 本身)，並連接到 $v_i$，令 $P’$ 為 $s$ 抵達 $u_i$ 的子路徑，則我們可以用以下不等式證明 $l(P) \geq \pi(u_{n+1})$：$$
\begin{aligned}
l(P) &\geq l(P’) + l(u_i, v_i) \hspace{2cm} (1) \\
& \geq \pi(u_i) + l(u_i, v_i) \hspace{2cm} (2) \\
& \geq \pi(v_i) \hspace{4.82cm} (3) \\
& \geq \pi(u_{n + 1}) \hspace{4.1cm} (4)
\end{aligned}
$$ 首先 $(1)$ 很直觀因為距離皆為正，因此 $P$ 路徑所需距離必定會大於子路徑的距離。而不等式 $(2)$，根據我們的假設 $\pi(u_i)$ 已經找到最短路徑，因此 $l(P’) \geq \pi(u_i)$。要說明不等式 $(3)$ 必須回想一下演算法，每次迭代找到最新的 $u$ 時，我們都會更新 $u$ 的鄰近點：$$
\begin{aligned}
\pi (v_i) &= \min (\pi (v_i), \pi (u_1) + l(u_1, v_i)) \\
\pi (v_i) &= \min (\pi (v_i), \pi (u_2) + l(u_2, v_i)) \\
&\vdots \\
\pi (v_i) &= \min (\pi (v_i), \pi (u_n) + l(u_n, v_i))
\end{aligned}
$$ 因此目前在 $\pi(v_i)$ 的路徑長度會被 $u_1, …, u_n$ 更新過。另外，若其中某一個點 $u$ 沒有和 $v_i$ 連結，路徑會設為無限大 $l(u, v) = \infty$，所以不用擔心這些狀況會影響結果。我們可以將所有迭代的結果整合成一條式子：$$
\pi(v_i) = \min (\pi(u_1) + l(u_1, v_i), …, \pi(u_n) + l(u_n, v_i))
$$ 因此不等式 $(3)$ 成立。最後，因為 $u_{n+1}$ 是從所有非 $\mathbf{S}$ 集合中找出擁有最短路徑的點 $u_{n+1} = \arg \min_{v \in V-S} \pi (v)$，因此不等式 $(4)$ 成立。

依照上述不等式，我們可以得到以下結論：所有可以從 $s$ 走到 $u_{n+1}$ 的 $P$，其路徑長度一定會不小於 $\pi(u_{n+1})$，因此 $\pi(u_{n+1})$ 就是從 $s$ 走到 $u_{n+1}$ 的最短路徑 $d(u_{n+1}) = \pi(u_{n+1})$，因此當 $\mathbf{S}$ 中的點 $u_1, …, u_n$ 中的點皆找到最短距離的條件下，下一步加入的點 $u_{n+1}$ 也會是最短距離，最後透過歸納法得證每個迭代都是找到最短路徑。