# Dijkstra 演算法
Dijkstra 演算法是一個尋找最短路徑的演算法，可以對一張沒有負權邊的有向圖找出從原點到其他所有點的最短路徑距離
## 引入情境
假設位於台北市的你今天想從內湖高中騎車到捷運中山站附近吃拉麵，在每個路口都有幾條路任君挑選，你的 GPS 要如何找到最短路徑呢?
<center>
<img src="https://hackmd.io/_uploads/HJoWngusyx.png" style="margin: 0 auto; display: block; width: 600px">
<p class="text-center">
Google 地圖上建議的路線
</p>
</center>
其中一種方法就是列舉每條路，把每條路的距離都加起來，然後選其中一條加起來最小的路線。這種方法可以找到最短路徑，卻要花上許多時間去列舉，甚至也有可能列舉到一些不值得考慮的路線，比如說從內湖到花蓮再南迴騎回來。顯然地，有些選擇荒謬至極
因此我們會需要有效率的 Dijkstra 演算法來幫助我們解決這個問題
## 定義最短路徑問題
### 給定條件
設一張帶權有向圖 $G=(V, E)$，此圖具備一個將邊與正整數映射的權重函數 $w: E \to \mathbb{N}$。若有一條路徑 $p=\langle v_0, v_1, ..., v_k\rangle$，則路徑上所有邊的權重之和 $w(p)=\sum^k_{i=1}w(v_{i - 1}, v_i)$。而從 $u$ 到 $v$ 的最短路徑，我們可以這樣描述:
$\delta(u, v)=\begin{cases}
min\{w(p): \text{every} ~p ~\text{from}~ u ~\text{to}~ v\}, ~\text{if exist}
\\ \infty, ~\text{otherwise}
\end{cases}$
權重函數 $w(p)$ 可以描述的不僅僅可以描述距離，像是時間、成本、損失...等等都可以
### 「全點對」最短路徑問題 All Pairs Shortest Path Problem
「全點對」最短路徑問題 : 給定上述的條件，找到任兩節點 $(u, v)$ 的最短路徑權重和
正常來說，在電腦中，我們使用一個二維陣列來儲存點對與最短距離的映射 $\delta : V\times V \rightarrow \mathbb{N}$
### 「單源」最短路徑問題 Single Source Shortest Path Problem
「單源」最短路徑問題 : 先確定起點 $s$，求從 $s$ 到任何 $t$ 的最短路徑距離
在電腦中，我們使用一個一維陣列來儲存 $s$ 與其他節點最短距離的映射
此問題可以有許多變體:
- 單終點最短路徑問題: 確定終點 $t$，求所有點 $s$ 到終點 $t$ 的最短路徑距離
- 單對最短路徑問題: 確定起點 $s$ 與終點 $t$，找出從 $s$ 到 $t$ 的最小權重和
## Dijkstra 演算法
### 性質: 最短路徑的子路徑是最短路徑
#### 敘述
設一張帶權有向圖 $G=(V, E)$，此圖具備一個將邊與正整數映射的權重函數 $w: E \to \mathbb{N}$。設 $p=\langle v_0, v_1, ..., v_k\rangle$ 為從 $v_0$ 到 $v_k$ 的最短路徑，$i, j$ 滿足 $0\leq i\leq j\leq k$，假設從 $v_i$ 到 $v_j$ 的路徑 $p_{i, j}=\langle v_i, v_{i+1}, ..., v_j\rangle$ 是 $p$ 的子路徑，則 $p_{i, j}$ 是從 $v_i$ 到 $v_j$ 的最短路徑
#### 證明
將 $p$ 拆解成 $p_{0, i}, ~p_{i, j}, ~p_{j, k}$，使得 $w(p)=w(p_{0, i}) + w(p_{i, j}) + w(p_{j, k})$。我們可以使用反證法證明之。假設 $p_{i, j}$ 不是從 $v_i$ 到 $v_j$ 的最短路徑，則存在一條從 $v_i$ 到 $v_j$ 的路徑 $p_{i, j}'$，使權重 $w(p_{i, j}') < w(p_{i, j})$，則 $p_{0, i}, ~p_{i, j}', ~p_{j, k}$ 是一條從 $v_0$ 到 $v_k$ 的路徑，其權重 $w(p_{0, i}) + w(p_{i, j}') + w(p_{j, k})<w(p)$，這與「$p$ 從 $v_0$ 到 $v_k$ 的最短路徑」矛盾
因此 $p_{i, j}$ 是從 $v_i$ 到 $v_j$ 的最短路徑
### 鬆弛 Relax
由 $\delta$ 的定義，設一起點 $s$，對於任何邊 $(u, v)$ 而言，必須符合三角不等式 $\delta(s, v)\leq \delta(s, u) + w(u, v)$。在單源最短路徑的演算法中，若我們搜尋到的邊不符合三角不等式，我們就需要把它替換掉，就如同我們求最小值的技巧一樣
```cpp
/* 此為 Pseudocode */
/* d 存兩點之間的最短距離, w 存邊權 */
Relax(u, v, w)
if d[s][u] > d[u][v] + w[u][v] :
d[s][u] = d[u][v] + w[u][v]
```
Dijkstra 演算法與 Bellman-Ford 演算法的精華就是這個步驟，接下來會大量使用這個性質
~~至於為什麼三角不等式會成立，可以很顯然看出~~
### 演算法
要找出一張圖的最短路徑，首先我們需要有個起點 $s$，接下來必須拿出 [BFS](https://hackmd.io/@ShanC/bfs_dfs#%E5%BB%A3%E5%BA%A6%E5%84%AA%E5%85%88%E6%90%9C%E5%B0%8B-Breadth-first-Search) 來探索所有節點。Dijkstra 演算法與 BFS 有許多雷同之處，可以考慮在每次準備探索一個新節點時，優顯選擇當前待拜訪名單 (queue) 中邊權之和最小的節點來拜訪並鬆弛
為了找到目前權重之和最小的節點，我們需要維護一個陣列 $d[u]$ 存取當前從 $s$ 到 $u$ 的最小邊權和。此資料結構必須要初始化為 $\infty$、起點設為 $0$，這樣才能找最小值
以下圖為例，設 $s=a$
<center>
<img src="https://hackmd.io/_uploads/rkK34B_skl.png" style="margin: 0 auto; display: block; width: 400px">
</center>
$~$
接下來會從 $a$ 拜訪 $b$ 與 $c$，更新 $d[~]$，並優先選擇 $b$ 拜訪
<center>
<img src="https://hackmd.io/_uploads/r1-uBSOjyg.png" style="margin: 0 auto; display: block; width: 400px">
</center>
$~$
在從 $b$ 拜訪 $c$ 時，會發現可以鬆弛，所以更新使 $d[c]=4$ 並拜訪
<center>
<img src="https://hackmd.io/_uploads/rJ7zIHdj1x.png" style="margin: 0 auto; display: block; width: 400px">
</center>
$~$
接下來還有 $e_{a,c}$ 尚未走過，走了之後會發現 $c$ 已經拜訪。如此一來這張圖就探索完了，從起點 $s=a$ 到其他節點的距離也都完成計算，可以將 $d$ 回傳
$~$
以下例子的圖比較大，可以幫助我們理解整個流程
<center>
<img src="https://hackmd.io/_uploads/S1qfoH_jyl.png" style="margin: 0 auto; display: block; width: 600px">
<p >
圖源: Introduction to Algorithms, Fourth Edition, p.621
</p>
</center>
### Dijkstra 演算法的限制
**Dijkstra 演算法不可使有負的邊權**。我們可以由一個簡單的例子來說明
<center>
<img src="https://hackmd.io/_uploads/SyVXn4dj1e.png" style="margin: 0 auto; display: block; width: 400px">
</center>
$~$
在此圖中起點為 $a$，根據我們的演算法，會先找到 $c$ 並記錄 $d[c]=1$。接下來走到 $b$ 紀錄 $d[b]=3$，之後走到 $c$，因 $c$ 已被拜訪，所以不會被鬆弛。最後得到 $a, c$ 的最短路徑長為 $1$。然而我們可以發現若從 $a$ 經過 $b$ 到 $c$ 這條路徑可以得到的權重和為 $0$ 而不是 $1$，此演算法得到錯誤的結果
會有這個問題是因為正整數只會越加越大，Dijkstra 就是利用此性質運作。若圖中有負邊使邊權之和變小，Dijkstra 就無法正常運作
### 實作程式碼
- 以下程式碼以鄰接陣列來維護
- 為了讓 queue 中每次取出來都是「當前邊權和最小的節點」，我們可以使用 `priority_queue` 來維護
- 由於要以「當前邊權和最小的節點」排序，我們可以把 `pair` 中的兩個值反著放
```cpp
typedef long long ll; // 有時邊權會很大，可以用 long long 來處理
typedef pair<ll, ll> pii;
vector<pii> g[N]; // g[u] = {v, w}: u 為起點, v 為終點, w 為路權
bool vis[N]; // 紀錄該節點是否走過
vector<ll> dijkstra(int s) { // 起點
// INF 要設為比可能的最短路徑權重還要大的值
vector<ll> d(N, INF);// 初始化
d[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq; // 小的在最前面
// {w, v}: w 為路權 v 為節點
pq.push({d[s], s});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) // 走過的不要再走
continue;
vis[u] = true;
for (pii i : g[u]) {
int v = i.first, w = i.second;
if (d[u] + w < d[v]) { // 鬆弛
d[v] = d[u] + w;
pq.push({d[v], v}); // 放入待拜訪名單
}
}
}
return d;
}
```
### 無路徑性質
若 $s$ 無法到達節點 $v$，那麼 `d[v]`$=\delta(s, v)=\infty$
### 上限性質
對於所有 $v\in V$，`d[v]` $\geq\delta(s, v)$，且一旦 `d[v]` $=\delta(s, v)$ 時，就不會改變
這可以用歸納法證明之，在此就不多贅述
### 收斂性質
如果對 $u, v\in V$，s 藉由 $u$ 到 $v$ 為最短路徑，且如果在鬆弛邊 $(u, v)$ 之前的任何時候 `d[u]` $=\delta(s, u)$，則在鬆弛之後的任何時候也 `d[u]` $=\delta(s, u)$
### Dijkstra 演算法的正確性
在演算法結束時，對於所有節點 $u$ 來說，`d[u]` 與 $\delta(s, u)$ 相同
#### 證明
我們先將程式碼中的布林陣列 `vis` 以一個集合 $S$ 替代之，對於任何節點 $u$ 而言，若 `vis[u]==true` 則 $u\in S$，否則 $u\notin S$。程式碼的其他 `vis` 都以這種方式改寫
在每次 `while` 迴圈開始迭代時，對於所有 $v\in S$ 而言，會得到 `d[v]` = $\delta(s, u)$，並將 $v$ 加入 $S$ 當中。最終演算法會在 $S=V$ 時結束，且對所有 $v\in V$，`d[v]` $=\delta(s, v)$。我們對 `while` 迴圈使用歸納法證明之
- Basis Step : 當 $|S| = 1$ 時，$S=\{s\}$，`d[s]`$=\delta(s, s) = 0$
- Induction Step : 假設對於所有 $v\in S$，`d[v]` $=\delta(s, v)$。演算法每次從 $V-S$ 中拿出節點 $u$，我們需要證明將 $u$ 放入 $S$ 時，`d[u]` $=\delta(s, u)$
設 $y$ 是 $s$-$u$ 最短路徑上第一個不在 $S$ 裡的節點，並且 $x$ 是此最短路徑上比 $y$ 早出現的節點 (有可能 $x=s$ 或 $y=u$)。由於 $y$ 在最短路徑上出現的時間早於或等於 $u$，且所有邊權都是正數，因此 $\delta(s, y) \leq \delta(s, u)$。因為在程式碼當中，`pq.top().second` 所回傳的 $u$ 會有最小的 $d$ 值，所以 `d[u]` $\leq$ `d[y]`，根據上述特性，可以知道 $\delta(s, u)\leq$ `d[u]`。又因為 $x\in S$，在假設中，我們已經知道 `d[x]` $=\delta(s, x)$
根據收斂性質，在邊 $(x, y)$ 被拜訪時已經鬆弛，得到 `d[y]` $=\delta(s, y)$，又 $\delta(s, y)\leq \delta(s, u)\leq$ `d[u]` $\leq$ `d[y]`，結合在一起可得 $\delta(s, y)= \delta(s, u)=$ `d[u]` $=$ `d[y]`。因此，`d[u]`$=\delta(s, u)$，根據上限性質，此值不會再改變
<center>
<img src="https://hackmd.io/_uploads/SkwnmuZ3Jl.png" style="margin: 0 auto; display: block; width: 550px">
</center>
### 時間複雜度分析
不同的 heap 會有不同的時間複雜度
- Unsorted Priority Queue : $O((V + E)~log ~V)$
- Fibonacci heap : $O(V~log ~V + E)$
- Binary heap : $O((V + E)~log ~V)$
## 備註
- 此演算法算是一種貪心法 (greedy method)
- 若看成是某種狀態轉移，那麼也算是種動態規劃 (dynamic programming)
## 題目練習
[CSES Shortest Routes I](https://cses.fi/problemset/task/1671) (裸的)
[Zerojudge a874. 14. Trace Route](https://zerojudge.tw/ShowProblem?problemid=a874) (裸的)
[Zerojudge c187. 10986 - Sending email](https://zerojudge.tw/ShowProblem?problemid=c187) (跟 a874 差不多裸)
[Zerojudge q100. 超能星球 (Planet)](https://zerojudge.tw/ShowProblem?problemid=q100) (建圖很麻煩)
[Zerojudge d793. 00929 - Number Maze](https://zerojudge.tw/ShowProblem?problemid=d793) (經典網格題，放在這裡讓你想想怎麼建圖)
[Zerojudge g422. PD.紅血球的快遞任務](https://zerojudge.tw/ShowProblem?problemid=g422)
[AtCoder Regular Contest 084 D - Small Multiple ](https://atcoder.jp/contests/arc084/tasks/arc084_b) (要把每個位元之間的轉換想成是一種狀態轉換)
----
## 參考資料
- Introduction to Algorithms, Fourth Edition
- [海大競程 - 2025 Shortest Path最短路徑](https://hackmd.io/@LeeShoWhaodian/HyT4ib5qJg#/4)
- [台師大演算法筆記 - Path](https://web.ntnu.edu.tw/~algo/Path.html)
- [J.H.Hung - CH7 Dijkstra Algorithm](https://hackmd.io/@iSpjX0WSTSKt_ZgHHoMg1Q/Sy70RvW52)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/3/8
Sign in with Wallet
Connect another wallet