<style>
.reveal .slides {
text-align: left;
font-size:35px;
}
</style>
# Shortest Path
## 最短路徑
Introduction to Competitive Programming
3/12 I2CP
----
## Table of Contents
- 複習: 圖論名詞
- 複習: 帶權邊存圖技巧
- 最短路徑問題
- Dijkstra's Algorithm
- Bellman-Ford Algorithm
- Floyd-Warshall Algorithm
---
### 複習: 圖論名詞
<div style="position: absolute; right: 0%; top:0%;">
</div>
<div style="position: absolute; left: 0%; top:100%;">
- {圖|graph}: $G=(V, E)$
- {節點|vertex}: $v\in V$ 又稱「點」
- {邊|edge}: $e \in E$
又分為「有向邊」、「無向邊」
- {邊權|weight}: $w: E\to\mathbb{Z}$
又稱為「花費」(cost)
</div>
----
<div style="position: absolute; left: 15%; top:60%;">
</div>
<div style="text-align: center;">圖也有分有向圖和無向圖</div>
----
### 環 (Cycle)
<div style="position: absolute; left: 15%; top:60%;">
</div>
---
## 複習: 帶權邊存圖技巧
- 鄰接矩陣
- 鄰接串列
- 邊陣列
----
### 鄰接矩陣
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
</div>
$5\leftrightarrow 6$ 花費為 $9$，表示為: $\text{matrix}[5][6] = \text{matrix}[6][5] = 9$
----
### 鄰接矩陣--存圖
- 有向
```cpp!
int dis[N][N];
void add_edge(int u,int v,int w){ // 起點 u、終點 v、權重 w
dis[u][v] = w;
}
```
- 無向
```cpp!
int dis[N][N];
void add_edge(int u,int v,int w){ // 連接 u 和 v、權重 w
dis[u][v] = w;
dis[v][u] = w;
}
```
----
### 鄰接串列
$1 \to 3$ 權重為 $5$，表示為 $1 : \{3, 5\}$
<div style="position: absolute; right: 5%; top:80%;">
</div>
<div style="position: absolute; left: 0%; top:80%;">
</div>
----
### 鄰接串列--存圖
- 有向
```cpp!
vector<pair<int,int>>graph[N]; // pair 存 {終點,權重}
void add_edge(int u,int v,int w){ // 起點 u、終點 v、權重 w
graph[u].push_back({v,w});
}
```
- 無向
```cpp!
vector<pair<int,int>>graph[N]; // pair 存 {終點,權重}
void add_edge(int u,int v,int w){ // 連接 u 和 v、權重 w
graph[u].push_back({v,w});
graph[v].push_back({u,w});
}
```
----
### 邊陣列
```cpp=
struct Edge{
int u, v, w;
}edge[100005];
for(int i = 0; i < m; i++){
cin >> edge[i].u >> edge[i].v >> edge[i].w;
}
```
---
## {最短路徑問題|Shortest Path Problem}
通常會有一張圖，
要你算從起點 $s$ 走到終點 $t$ 所需的最小花費 (權重) 總和
----
$4\to 3\to 5$ 的花費是 $1+3=4$
$2\to 5\to 3$ 的花費是 $4+3=7$
----
$4\to 3\to 5\to 1$ 的花費是 $1+3+1=5$ (最短路徑)
$4\to 3\to 1$ 的花費是 $1+5=6$
----
同一起點、終點之間可能會有多條路徑，
最短路徑就是其中權重和 (花費) 最小的路徑
----
如果存在負環那麼就可以走到{無限小的花費|可能不存在最短路徑}
有沒有負環也是最短路徑問題須考慮的一點
----
在最短路徑這個演算法上我們要對應不同的圖
使用合適的演算法
----
### 正式定義{花費|Cost}
給一個加權的圖 $G=(V,E)$，權重函數 $w:E\to\mathbb{Z}$
路徑 $p=\langle v_0,\cdots,v_{k}\rangle$ 的花費為:
$$
w(p)=\sum_{i=1}^{k} w(v_{i-1},v_i)
$$
----
### 正式定義{最短路徑|Shortest Path}
從 $u$ 到 $v$ 最小花費為:
$$
\delta(u,v)=
\begin{cases}
&\min\{w(p): u\sim^p v\}&\text{if 存在路徑從 u 到 v}\\
&\infty&\text{if 沒有}\\
\end{cases}
$$
從 $u$ 到 $v$ 的**最短路徑**是滿足 $w(p)=\delta(u,v)$ 的**任何路徑** $p$
----
### 最短路徑分類
- {單源|Single Source}{最短路徑|Shortest Path} (固定起點、不固定終點)
- {全點對|All-pairs}{最短路徑|Shortest Path} (不固定起點、不固定終點)
----
### 單源最短路徑
給你一個圖，一個起點 $s$，
求出這個起點到每個點 $v$ 的最短路徑 $\delta(s, v)$
<div style="position: absolute; left: 28%; top:80%;">
</div>
----
### 全點對最短路徑
給你一個圖，多組起點和終點 $(s_i, t_i)$，
求出每組起點到終點的最短路徑 $\delta(s_i, t_i)$
<div style="position: absolute; left: 20%; top:80%;">
</div>
----
### 演算法們
- 單源最短路徑
- Dijkstra
- Bellman-Ford
- 全點對最短路徑
- Floyd-warshall
---
## 最短路徑的性質
----
### {三角不等式|Triangle Inequality}
給定起點 $s$ 對於任意邊 $(u,v)\in E$，
$$
\delta(s,v)\le \delta(s,u)+w(u,v)
$$
----
在單源最短路徑中，會先創一個陣列 $\text{dis}[]$，起點設 $s$
一開始會把 $\text{dis}[s]$ 設為 $0$，代表起點到自己的距離是 $0$
然後把到其他點 $u$ 的值 $\text{dis}[u]$ 設為 $\infty$
----
### {鬆弛|Relax}
假設現在走到 $u$，如果存在一個邊 $u\to v$，使得
$$
\text{dis}[v] > \text{dis}[u] + w(u, v)
$$
那麼我們可以更新 $\text{dis}[v] = \text{dis}[u] + w(u, v)$
這樣子我們稱透過 $(u,v)$ 進行了一次鬆弛
<!-- .element: class="fragment" data-fragment-index="1" -->
----
假設起點 $s=2$，$\text{dis}[3] = 5$，
由於 $\text{dis}[3] > \text{dis}[1] + w(1, 3),\quad (\because 5 > 4)$，
我們更新 $\text{dis}[3] = 4$
----
假設現在已經沒有邊給 $\text{dis}[~]$ 鬆弛了
比較一下三角不等式與最終的{陣列|起點為$s$的} $\text{dis}[~]$:
$$
\begin{split}
&\text{三角不等式: }&\delta(s,v)&\le \delta(s,u)+w(u,v)\\
&\text{陣列: }&\text{dis}[v] &\le \text{dis}[u] + w(u, v)
\end{split}
$$
我們做鬆弛的目的，
其實是讓 $\text{dis}[~]$ 陣列最終滿足三角不等式
<!-- .element: class="fragment" data-fragment-index="1" -->
---
## Dijkstra's Algorithm
----
### 想法
起點設 $s$，定義陣列 $\text{dis}[~]$:
$$
\text{dis}[i]=
\begin{cases}
0\quad & \text{if }i=s\\
\infty & \text{otherwise}\\
\end{cases}
$$
重複做下面的步驟:
1. 選一個離起點最近並且沒有走過的點 $u$
2. 把點 $u$ 設定為走過
3. 透過所有連接點 $u$ 和 $v$ 的邊，去鬆弛點 $v$
----
學會鬆弛之後我們就可以看看 Dijkstra 在做什麼了
假設一開始起點 $s=2$，要算下圖的最短距離
----
### 初始化
先把dis初始化，把起點設為0，其他設為INF(很大的數字)
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | INF | 0 |
| 2 | | 0 | 0 |
| 3 | | INF | 0 |
| 4 | | INF | 0 |
| 5 | | INF | 0 |
| 6 | | INF | 0 |
</div>
----
1. <span style="color: red">選一個離起點最近並且沒有走過的點$u$ $\to$ 選 $2$</span>
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | INF | 0 |
| 2 | | 0 | 0 |
| 3 | | INF | 0 |
| 4 | | INF | 0 |
| 5 | | INF | 0 |
| 6 | | INF | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. <span style="color: red">把點$u$設定為走過 $\to$ $\text{visited}[2]=1$</span>
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | INF | 0 |
| 2 | | 0 |<span style="color: red">1</span>|
| 3 | | INF | 0 |
| 4 | | INF | 0 |
| 5 | | INF | 0 |
| 6 | | INF | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. <span style="color: red">透過所有連接點$u$和$v$的邊，去鬆弛點$v$</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | INF | 0 |
| 2 | | 0 |<span style="color: red">1</span> |
| 3 | | INF | 0 |
| 4 | | ~~INF~~ <span style="color: red">1</span> | 0 |
| 5 | | INF | 0 |
| 6 | | ~~INF~~ <span style="color: red">7</span> | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | INF | 0 |
| 2 | | 0 |<span style="color: red">1</span>|
| 3 | | INF | 0 |
| 4 | | 1 | 0 |
| 5 | | INF | 0 |
| 6 | | 7 | 0 |
</div>
----
1. <span style="color: red">選一個離起點最近並且沒有走過的點$u$ $\to$ 選4</span>
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | INF | 0 |
| 2 | | 0 |<span style="color: red">1</span>|
| 3 | | INF | 0 |
| 4 | | 1 | 0 |
| 5 | | INF | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. <span style="color: red">把點$u$設定為走過 $\to \text{visited}[4]=1$</span>
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | INF | 0 |
| 2 | | 0 |<span style="color: red">1</span> |
| 3 | | INF | 0 |
| 4 | | 1 |<span style="color: red">1</span> |
| 5 | | INF | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. <span style="color: red">透過所有連接點$u$和$v$的邊，去鬆弛點$v$</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | ~~INF~~ <span style="color: red">5</span> | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | ~~INF~~ <span style="color: red">2</span> | 0 |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | ~~INF~~ <span style="color: red">5</span>| 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | 0 |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 5 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. <span style="color: red">選一個離起點最近並且沒有走過的點$u$ $\to$ 選$3$</span>
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | 0 |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 5 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. <span style="color: red">把點$u$設定為走過 $\to$ $\text{visited}[3]=1$</span>
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 5 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. <span style="color: red">透過所有連接點$u$和$v$的邊，去鬆弛點$v$</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | ~~5~~ <span style="color: red">4</span> | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. <span style="color: red">選一個離起點最近並且沒有走過的點$u\to$ 選$5$</span>
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. <span style="color: red">把點u設定為走過 $\to \text{visited}[5]=1$</span>
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. <span style="color: red">透過所有連接點$u$和$v$的邊，去鬆弛點$v$</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | 0 |
</div>
----
1. <span style="color: red">選一個離起點最近並且沒有走過的點$u$ $\to$ 選$1$</span>
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | 0 |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. <span style="color: red">把點u設定為走過 $\to \text{visited}[1]=1$</span>
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | <span style="color: red">1</span> |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. <span style="color: red">透過所有連接點$u$和$v$的邊，去鬆弛點$v$</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | <span style="color: red">1</span> |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | 0 |
</div>
----
1. <span style="color: red">選一個離起點最近並且沒有走過的點$u$ $\to$ 選$6$</span>
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | <span style="color: red">1</span> |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. <span style="color: red">把點$u$設定為走過 $\to$ $\text{visited}[1]=1$</span>
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | <span style="color: red">1</span> |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | <span style="color: red">1</span> |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. <span style="color: red">透過所有連接點$u$和$v$的邊，去鬆弛點$v$</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | <span style="color: red">1</span> |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | <span style="color: red">1</span> |
</div>
----
這樣就走完ㄌ
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | <span style="color: red">1</span> |
| 2 | | 0 | <span style="color: red">1</span> |
| 3 | | 2 | <span style="color: red">1</span> |
| 4 | | 1 | <span style="color: red">1</span> |
| 5 | | 4 | <span style="color: red">1</span> |
| 6 | | 7 | <span style="color: red">1</span> |
</div>
----
分析一下可能的複雜度，以下假設$V$為點個數，$E$為邊個數
1. 初始化 $\to$<!-- .element: class="fragment" data-fragment-index="1" --> $O(V)$<!-- .element: class="fragment" data-fragment-index="1" -->
2. 選一個離起點最近並且沒有走過的點 $u$ $\to$<!-- .element: class="fragment" data-fragment-index="2" --> $O(V \cdot V)$<!-- .element: class="fragment" data-fragment-index="2" -->
3. 把點 $u$ 設定為走過 $\to$<!-- .element: class="fragment" data-fragment-index="3" --> $O(V \cdot 1)$<!-- .element: class="fragment" data-fragment-index="3" -->
4. 透過所有連接點 $u$ 和 $v$ 的邊，去鬆弛點 $v$ $\to$<!-- .element: class="fragment" data-fragment-index="4" --> $O(E)$<!-- .element: class="fragment" data-fragment-index="4" -->
總複雜度：<!-- .element: class="fragment" data-fragment-index="5" -->$O(V^2+E)$<!-- .element: class="fragment" data-fragment-index="5" -->
----
### 來看這個[例題](https://cses.fi/problemset/task/1671)
給你一個圖，圖上有$V$個點，$E$條邊，給定起點問你這個起點到每個點的最短距離。
$1 \le V\le10^5$，$1 \le E\le 2\cdot 10^5$
----
顯然剛剛的做法砸下去就會過了，那複雜度呢？
$O(V^2+E)$<!-- .element: class="fragment" data-fragment-index="1" --> $\to$<!-- .element: class="fragment" data-fragment-index="1" --> $O(10^{10})$<!-- .element: class="fragment" data-fragment-index="1" --> $\to$<!-- .element: class="fragment" data-fragment-index="1" --> TLE<!-- .element: class="fragment" data-fragment-index="1" -->
----
看看有哪些步驟的複雜度可以被優化掉
1. 初始化 $\to$ $O(V)$
2. 選一個離起點最近並且沒有走過的點 $u$ $\to$ $O(V \cdot V)$
3. 把點$u$設定為走過 $\to O(V \cdot 1)$
4. 透過所有連接點 $u$ 和 $v$ 的邊，去鬆弛點 $v$ $\to$ $O(E)$
總複雜度：$O(V^2+E)$
----
看看有哪些步驟的複雜度是可以被優化掉的
1. 初始化 $\to$ $O(V)$
2. <span style="color: red">選一個離起點最近並且沒有走過的點 $u$ $\to$ $O(V \cdot V)$ </span>
3. 把點 $u$ 設定為走過 $\to O(V \cdot 1)$
4. 透過所有連接點 $u$ 和 $v$ 的邊，去鬆弛點 $v$ $\to$ $O(E)$
總複雜度：$O(V^2+E)$
----
可以搭配 priority_queue 這個 STL 工具來用
你可以把每個有被鬆弛過的點 $x$ 套成一個 pair，$(\text{dis}[x],x)$丟進priority_queue裡面，裡面會按照 $\text{dis}$ 去做排序
他可以幫你用 $O(\log V)$ 的時間知道哪個 $u$ 的 $\text{dis}[u]$ 是最小的
----
這時候的複雜度就會變成這樣
1. 初始化 $\to$ $O(V)$
2. <span style="color: green">選一個離起點最近並且沒有走過的點$u$ $\to$ $O(V \cdot \log V)$</span>
3. 把點$u$設定為走過 $\to$$O(V \cdot 1)$
4. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$ $\to$ $O(E)$
總複雜度：$O(V\log V+E)$
TLE 就解決了
----
範例code：
```cpp! [|6-9|10-11|13-14|15-16|17-22|]
#define pii pair<int,int>
#define INF 1e18
vector<pair<int,int>>vec[N];
void dijkstra(int s,int t){//起點，終點
int dis[N];
for(int i=0;i<N;i++){//初始化
dis[i]=INF;//值要設為比可能的最短路徑權重還要大的值
}
dis[s]=0;
priority_queue<pii,vector<pii>,greater<pii>>pq;//以小到大排序
pq.push({dis[s],s});
while(pq.empty()==0){
int u=pq.top().second;
pq.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,w]:vec[u]){
if(dis[u]+w<dis[v]){//鬆弛
dis[v]=dis[u]+w;
pq.push({dis[v],v});
}
}
}
}
```
複雜度：$O(V\log V+E)$
----
### 小限制
如果圖中有負權邊，Dijkstra 這個演算法不能用
因為 Dijkstra 會取 $\text{dis}$ 最小的點，在有負權邊的情況下會爛掉
----
起點為 $1$ 的時候會爛掉
----
若是邊權只有 $0$ 或 $1$，有沒有更好的優化方式？
----
<div style="position: absolute; left: 15%; top:80%;">
可以發現我們只要維持每次取出最小值，
因此可以使用 deque 取代 priority_queue
這樣可以保持 deque 內的{單調|monotonic}性質 (由小到大)
</div>
----
選一個離起點最近並且沒有走過的點
- 邊權為 $0$ $\to$ push_front()
- 邊權為 $1$ $\to$ push_back()
複雜度從 $O(\log V)$ 降低到 $O(1)$
這個技巧叫做 0-1 BFS
----
### 0-1 BFS
```cpp=
vector<pair<int, int>> vec[N];
deque<int> dq;
int dis[N];
for(int i = 0; i < N; i++) dis[i] = INF; // 初始化
dq.push_front(0, s), dis[s] = 0; // 記得起點 s 要設為 0
while(!dq.empty()) {
int u = dq.front(); // 取出當前最近的點
dq.pop_front();
for(auto [v, w] : vec[u]) {
if (dis[u] + w < dis[v]) { // 鬆弛
dis[v] = dis[u] + w;
if (w == 0) dq.push_front(v);
else dq.push_back(v);
}}}
```
----
### {最短路徑樹|Shortest Path Tree}
給定了一個起點，從這個起點走到任意的點的路徑會形成一棵樹(也有可能是多顆)
以下面的例子來說，最短路徑樹有兩顆
----
fun fact: 最短路徑樹是一棵生成樹!!
複習一下[樹的其中一種定義方式](https://hackmd.io/@LeeShoWhaodian/2025-Graph-Theory#/4/13):
- 無自環且任兩點僅存在唯一路徑的圖
對於每個點 $v$，可以挑選一條從 $s$ 到 $v$ 的最短路徑放進子圖 $T$
如此一來 $T$ 當然可以符合此定義 ($T$ 是樹)
且因為 $T$ 包含所有節點，因此 $T$ 是**生成樹**
---
## 下課時間
---
## Bellman-Ford
----
### 想法
Bellman-Ford 是以每一條邊去做鬆弛，
能鬆弛就直接去做鬆弛，直到不能鬆弛為止
<div style="position: absolute; left: 20%; top:80%;">
</div>
----
不難發現由於一條最短路最多會經過 $n-1$ 條邊，
因此只要對每個邊鬆弛 $n-1$ 次就好
<div style="position: absolute; left: 20%; top:80%;">
</div>
----
考慮使用邊陣列，以每一條邊去做鬆弛
```cpp!
for (int i = 0; i < m; i++){
if (dis[edge[i].u] + edge[i].w < dis[edge[i].v]){
dis[edge[i].v] = dis[edge[i].u] + edge[i].w;
}
}
```
複雜度：總共 $m$ 條邊，鬆弛 $n-1$ 次 $\to O(nm)$
----
code:
```cpp!
for(int t = 1; t < n; t++){ // 注意: 這邊只需要跑 n-1 次，而不是 n 次
for (int i = 0; i < m; i++){
if (dis[edge[i].u] + edge[i].w < dis[edge[i].v]){
dis[edge[i].v] = dis[edge[i].u] + edge[i].w;
}
}
}
```
----
### {負環|Negative Cycle}
可以無限減少花費的一個環 ($1 \to 3 \to 2 \to 1$)
----
有負環的話 會發現可以無限進行鬆弛操作
----
### 判斷負環
若是第 $n$ 輪鬆弛還有點被鬆弛到$\Rightarrow$這張圖存在負環
----
### Shortest Path Faster Algorithm (SPFA)
其實是 Bellman-Ford 的優化版本
----
### 想法
可以發現 Bellman-Ford 有很多鬆弛操作是多餘的
只有上一次被鬆弛的節點，所連接的邊，才有可能引起下一次鬆弛
----
### code
我們用一個queue來維護「可能會引起鬆弛操作的節點」
```cpp=
struct edge {
int v, w;
};
int s, n; // 起點 點數量
vector<edge> E[MXN];
vector<int> dis(MXN, INF), cnt(MXN), inq(MXN);
// cnt記錄最短路經過幾條邊
// inq記錄節點是否在queue裡面
queue<int> Q;
dis[s] = 0; Q.push(s); inq[s] = 1;
while (Q.size()) {
int u = Q.front(); Q.pop();
inq[u] = 0;
for (auto [v, w] : E[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) {
// 有負環 因為一般最短路只會經過 n - 1 條邊
}
if (!inq[v]) Q.push(v), inq[v] = 1;
}
}
}
```
----
### 複雜度
在大部分時候 SPFA 跑的非常快
但其實最差的情況複雜度還是 $O(nm)$
當你發現 Bellman-Ford TLE 的時候
這個時候你就可以用 SPFA
---
## Floyd-Warshall
----
### 想法
對於點對 $(i,j)$，找 $i$ 走到 $j$ 的最短路時，可能存在中繼點 $k$
從 $i$ 走到 $k$ 加上 $k$ 走到 $j$ 的路徑可能會更短
<div style="position: absolute; left: 18%; top:80%;">
</div>
我們可以考慮用鄰接矩陣紀錄結果
----
注意到最佳子結構:
$p_1$ 與 $p_2$ 的所有點都屬於 $\{1,2,\cdots ,k-1\}$
$p$ 的所有點都屬於 $\{1,2,\cdots, k\}$
<div style="position: absolute; left: 18%; top:80%;">
</div>
----
### 定義
可以考慮 DP 來解問題:
$\text{dp}[k][i][j]$ 為從 $i$ 到 $j$ 只經過 $1\sim k$ 的最短距離
----
### 初始化
$$
\text{dp}[0][i][j]=
\begin{cases}
w_{ij}\quad & \text{, if} (i,j)\in E\\
0\quad & \text{, if } i=j\\
\infty\quad & \text{, otherwise}\\
\end{cases}
$$
----
### 轉移
```cpp!
for (k = 1; k <= n; k++) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
}
}
}
```
空間複雜度：$O(N^3)$ <!-- .element: class="fragment" data-fragment-index="1" -->$\leftarrow$這個空間有點糟<!-- .element: class="fragment" data-fragment-index="1" -->
時間複雜度：$O(N^3)$
正常來說我們不會這樣做
<!-- .element: class="fragment" data-fragment-index="2" -->
----
### 空間優化
可以發現轉移的時候有一維是可以省略掉
$$
\text{dp}[k][i][j] \to \text{dp}[i][j]
$$
所以空間複雜度可以優化到 $O(N^2)$
----
空間可以這樣優化是因為
在更新時並不會取用到其他資訊而影響計算
也就{是說在計算 $d_{ij}^{(k)}$|(這邊換個符號來節省空間)} 時，因 $d_{kk}^{(k-1)}=0$，所以:
$$
\begin{split}
\text{Case 1: }&d_{ik}^{(k)} = \min(d_{ik}^{(k-1)}, d_{ik}^{(k-1)} + d_{kk}^{(k-1)})=d_{ik}^{(k-1)}\\
\text{Case 2: }&d_{kj}^{(k)} = \min(d_{kj}^{(k-1)}, d_{kk}^{(k-1)} + d_{kj}^{(k-1)})=d_{kj}^{(k-1)}\\
\text{Case 3: }&d_{ij}^{(k)} = \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}), (i\neq k, k\neq j)
\end{split}
$$
----
<div style="position: absolute; left: 0%; top:100%;">
$\text{Case 1, 2}$ 通過證明發現不影響答案，
而 $\text{Case 3}$ 一定不影響
- $\text{Case 1}$ 就是紅色虛線框
- $\text{Case 2}$ 就是藍色虛線框
- $\text{Case 3}$ 就是其他的部分
</div>
<div style="position: absolute; right: 0%; top:100%;">
</div>
----
實作上，我們只會用輸入的矩陣 in-place 把答案算出來，
而不是開 $N$ 個矩陣
----
### 初始化和讀邊
- 自己到自己的距離為 $0$，否則為 INF
- 有一個有向邊為 $u$ 走到 $v$，權重為 $w$，更新 $\text{dis}[u][v]$
```cpp! [1-7|8-10]
int dis[N + 1][N + 1];
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
dis[i][j] = INF; // INF 就是很大的數
}
dis[i][i] = 0;
}
int u, v, w;
cin >> u >> v >> w;
dis[u][v]=min(dis[u][v], w);
```
初始化時間複雜度：$O(N^2)$
----
依序枚舉每個中繼點，再枚舉每個點對，順序是 $(k,i,j)$
```cpp!
for(int k=1;k<=N;k++){//窮舉中繼點k
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){//窮舉點對(i,j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
```
時間複雜度：$O(N^3)$
----
Floyd-Warshall 可以在時間複雜度 $O(N^3)$、空間 $O(N^2)$ 以內做完全點對最短路徑問題
基本上要做全點對最短路徑一定砸 Floyd-Warshall
---
### Summary
| 演算法 | 時間 | 存圖 | 備註 |
| --- | --- | --- | --- |
| Dijkstra | $O(V \log V)$ | priority_queue | No 負邊 |
|0-1 BFS | $O(V + E)$ | deque | $w=$ 0 or 1 |
| Bellman-Ford | $O(VE)$ | 邊陣列 | 可測負環 |
| SPFA | $O(VE)$ | queue | 快一點 |
| Floyd-Warshall | $O(V^3)$ | 鄰接矩陣 | 全點對 |
----
來練習8
{"title":"Shortest Path","image":"https://hackmd.io/_uploads/r1SO1_64Ze.png","description":"海大競程 2026 spring 上課講義 shortest path\n本章主要介紹三種演算法:\n- Dijkstra\n- Bellman-Ford\n- Floyd-Warshall\n除此之外還介紹了:\n- 0-1 BFS\n- SPFA \n等主題","contributors":"[{\"id\":\"4f67a8cd-06ae-45dc-a8e3-62c6a41e5a37\",\"add\":35782,\"del\":6067,\"latestUpdatedAt\":1769610954479}]"}