# 最短路徑問題 Shortest Path Problem
有些問題困擾我很久，就是很多文獻在講 shortest path 時都把 walk 跟 path 的概念混著使用。當初在讀 Bellman-Ford 時一直在想為什麼這樣會形成一個 "path"? 結果發現定義根本就不一樣。這讓我有了一個概念「如果連問題都定義不清不楚，那何必討論演算法呢?」事實上，要在數學上正式地、嚴謹地定義問題，是一門很重要的學問，但我們改天再來談談這件事
這篇的目的就是把最短路徑問題講清楚一點，另一方面也記錄我查到的資料避免我忘記。很多名詞我都在[這篇](https://hackmd.io/@ShanC/basic-graph-theory-2)有提過，就不再重複了
## 引入情境
假設位於台北市的你今天想從內湖高中騎車到捷運中山站附近吃拉麵，在每個路口都有幾條路任君挑選，你的 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>
其中一種方法就是列舉每條路，把每條路的距離都加起來，然後選其中一條加起來最小的路線。這種方法可以找到最短路徑，卻要花上許多時間去列舉，甚至也有可能列舉到一些不值得考慮的路線，比如說從內湖到花蓮再南迴騎回來。顯然地，有些選擇荒謬至極|| (但有時候我們又不得不這麼找)||
因此我們會需要有效率的演算法來幫助我們解決這個問題
## 單源自然數權重的最短路徑問題
### 給定條件
設一張帶權有向圖 $G=(V, E)$，此圖具備一個將邊與正整數映射的權重函數 $w: E \to \mathbb{N}$。若有一條路徑 (simple path) $p=\langle v_0, v_1, ..., v_k\rangle$，則路徑上所有邊的權重之和 $w(p)=\sum\limits^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)$ 可以描述的不僅僅可以描述距離，像是時間、成本、損失...等等都可以
### 單源最短路徑問題 Single Source Shortest Path Problem
「單源」最短路徑問題 : 先確定起點 $s$，求從 $s$ 到任何 $t$ 的最短路徑距離
在電腦中，我們使用一個一維陣列來儲存 $s$ 與其他節點最短距離的映射
此問題可以有許多變體:
- 單終點最短路徑問題: 確定終點 $t$，求所有點 $s$ 到終點 $t$ 的最短路徑距離
- 單對最短路徑問題: 確定起點 $s$ 與終點 $t$，找出從 $s$ 到 $t$ 的最小權重和
### 性質: 最短路徑的子路徑是最短路徑
這個性質給我們**最佳子結構**的條件，使我們可以用 [Dijkstra 演算法](https://hackmd.io/@ShanC/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}$ ($0<i<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$ 的最短路徑
## 有負權邊的情況
### 單源負權重邊的最短路徑問題
這裡有的設定都跟上面的相同，只是有負權重，也就是權重函數 $w: E\to \mathbb{Z}$
事實上，我們其實沒辦法直接求解單源負權重邊的最短路徑問題。如果我們硬要在「有負環」的圖中找一條最短的 simple path，這個問題會變成 NP-hard。因為這等同於在某些情況下解[「最長路徑問題」](https://en.wikipedia.org/wiki/Longest_path_problem)
### Walk?
負權邊會有種狀況叫做「負環」
<center>
</center>
這會使起點走到某些點可以無限的繞，也就是說，這種迴路會產生並沒有明確的「下限」因此我們定義: $\delta(s, v)=-\infty$。或者有時候是未定義
此外，由於這樣繞產生的不是一條{路徑|path}，而是一條{行走|walk}。可以想像在權重為自然數的情況下，數值只會**越加越大**，因此 walk 只會比 path 的差，我們不討論 walk。但是在有負值的情況下，walk 可能會是比 path 權重和更小的選擇。所以在負權邊的情況下，會把 path 的限制放寬成 walk，也就是點、邊可以重複走
### 我們能解決的問題
以下這些問題可以用 [Bellman-Ford 演算法](https://hackmd.io/@ShanC/Bellman-Ford-Algorithm)解決 :
- 在沒負環的圖上找出最短路徑
- 檢驗一張圖上是否有負環
這些才是我們真的能解決的問題
### 無環圖的單源負權重邊的最短路徑問題
如果加上**無環**的限制，那麼就不會有上述的問題，圖也自然會形成{有向 無環 圖|directed acyclic graph} (DAG)。在有向無環圖上，我們可以考慮使用 DP on DAG 的技巧推出轉移式:
$$
\text{dp}[v]=\min_{(u, v)\in E}\{\text{dp}[u]+w(u,v)\}
$$
## 全點對最短路徑問題 All Pairs Shortest Path Problem
全點對最短路徑問題 : 給定上述的條件，找到任兩節點 $(u, v)$ 的最短路徑權重和。這裡指的路徑是 simple path，也就是點、邊不能重複走的情況。正常來說，在電腦中，我們使用一個二維陣列來儲存點對與最短距離的映射 $\delta : V\times V \rightarrow \mathbb{Z}$
這個問題可以用 Floyd-Warshall 求解
## 鬆弛 Relax
### 說明
由 $\delta$ 的定義，設一起點 $s$，對於任何邊 $(u, v)$ 而言，必須符合三角不等式 :
$$
\delta(s, v)\leq \delta(s, u) + w(u, v)
$$
在最短路徑的演算法中，會維護一個距離陣列 `d[.][.]`。若我們搜尋到的邊不符合三角不等式，我們就需要把它替換掉，就如同我們求最小值的技巧一樣
```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]
```
### 亂亂講
有了鬆弛機制後，我們該如何求出 $s$ 到所有點的最短距離呢? 我們有非常多種選擇:
- 對所有邊都鬆弛 (可能要鬆弛很多次?)
- 對所有點的鄰居都鬆弛 (順序該如何決定?)
- 若給定點 $u$ 與點 $v$，因為兩點間可能有很多中繼點，或許可以去鬆弛所有中繼點?
我們在之後的最短路徑演算法會一直用到這個機制
## 後記
會有這篇是因為我在準備[海大競程2026講義](https://hackmd.io/@LeeShoWhaodian/2026-shortest-path#/)時，對於學長們傳承下來的簡報的很多細節很有意見。但海大的 I2PC 一門注重實作與刷題的課，講那麼對競賽沒有幫助的東西，實在有點不妥。因此握把遺珠之憾都搬過來講
目前我的筆記有更新了 [Dijkstra 演算法](https://hackmd.io/@ShanC/Dijkstra)、[Bellman-Ford 演算法](https://hackmd.io/@ShanC/Bellman-Ford-Algorithm)的介紹與性質，可以去看
----
## 參考資料
- 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
> 更新: 2026/1/25
Sign in with Wallet
Connect another wallet