<!-- ---
type: slide
--- -->
<style>
.reveal .slides {
text-align: left;
font-size:35px;
}
</style>
# Shortest Path最短路徑
3/6
---
### 什麼是最短路徑?
通常會有一張圖，要你算從起點$s$走到終點$t$所需的最小時間or花費
----
像是4走到5的時間/花費是4
或是2走到3的時間/花費是7
----
圖也有分有向圖和無向圖
----
或是有負環或是沒負環
在最短路徑這個演算法上我們要對應不同的圖
使用合適的演算法
---
## 存圖技巧
- 鄰接矩陣
- 鄰接串列
----
## 鄰接矩陣
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
</div>
5 <-> 6 花費為 9
matrix[5][6] = 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、權重whttps://hackmd.io/_uploads/BytUT8996.png
dis[u][v]=w;
dis[v][u]=w;
}
```
----
## 鄰接串列
1 -> 3 權重為 5
表示為 1 : {3, 5}
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
</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});
}
```
---
## 最短路徑分類
- 單源最短路徑(固定起點、不固定終點)
- 全點對最短路徑(不固定起點、不固定終點)
----
## 單源最短路徑
給你一個圖，一個起點，求出這個起點到每個點的最短路徑
----
## 全點對最短路徑
給你一個圖，多組起點和終點，求出每組起點到終點的最短路徑
----
## 演算法們
- 單源最短路徑
- Dijkstra
- Bellman-Ford
- 全點對最短路徑
- Floyd-warshall
---
## Dijkstra
----
## 想法
由於是單源最短路徑，所以會先創一個陣列，這裡叫dis
一開始會把dis[起點]設為0，代表起點到自己的距離是0
然後把dis[其他點]設為INF，再重複做下面的步驟
1. 選一個離起點最近並且沒有走過的點$u$
2. 把點$u$設定為走過
3. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$
----
## 什麼是鬆弛
假設 dis[u][v] = x，如果存在一個點e
使得x > dis[u][e] + dis[e][v]
那麼我們可以更新dis[u][v] = dis[u][e] + dis[e][v]
這樣子我們稱透過e進行了一次鬆弛
----
dis[2][3] = 5
因為 dis[2][3] > dis[2][1] + dis[1][3] (5 > 4)
我們更新 dis[2][3] = 4
----
學會鬆弛之後我們就可以看看Dijkstra在做什麼了
假設一開始起點是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. `選一個離起點最近並且沒有走過的點u` $\to$ `選2`
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. `把點u設定為走過` $\to$ `visited[2]=1`
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 | `1` |
| 3 | | INF | 0 |
| 4 | | INF | 0 |
| 5 | | INF | 0 |
| 6 | | INF | 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 | `1` |
| 3 | | INF | 0 |
| 4 | | ~~INF~~ `1` | 0 |
| 5 | | INF | 0 |
| 6 | | ~~INF~~ `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 | | INF | 0 |
| 2 | | 0 | `1` |
| 3 | | INF | 0 |
| 4 | | 1 | 0 |
| 5 | | INF | 0 |
| 6 | | 7 | 0 |
</div>
----
1. `選一個離起點最近並且沒有走過的點u` $\to$ `選4`
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 | `1` |
| 3 | | INF | 0 |
| 4 | | 1 | 0 |
| 5 | | INF | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. `把點u設定為走過` $\to$ `visited[4]=1`
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 | `1` |
| 3 | | INF | 0 |
| 4 | | 1 | `1` |
| 5 | | INF | 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 | | ~~INF~~ `5` | 0 |
| 2 | | 0 | `1` |
| 3 | | ~~INF~~ `2` | 0 |
| 4 | | 1 | `1` |
| 5 | | ~~INF~~ `5`| 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 | `1` |
| 3 | | 2 | 0 |
| 4 | | 1 | `1` |
| 5 | | 5 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. `選一個離起點最近並且沒有走過的點u` $\to$ `選3`
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 | `1` |
| 3 | | 2 | 0 |
| 4 | | 1 | `1` |
| 5 | | 5 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. `把點u設定為走過` $\to$ `visited[3]=1`
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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 5 | 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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | ~~5~~ `4` | 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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. `選一個離起點最近並且沒有走過的點u` $\to$ `選5`
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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | 0 |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. `把點u設定為走過` $\to$ `visited[5]=1`
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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 6 | | 7 | 0 |
</div>
----
1. `選一個離起點最近並且沒有走過的點u` $\to$ `選1`
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 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. `把點u設定為走過` $\to$ `visited[1]=1`
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 | `1` |
| 2 | | 0 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 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 | `1` |
| 2 | | 0 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 6 | | 7 | 0 |
</div>
----
1. `選一個離起點最近並且沒有走過的點u` $\to$ `選6`
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 | `1` |
| 2 | | 0 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 6 | | 7 | 0 |
</div>
----
1. 選一個離起點最近並且沒有走過的點$u$
2. `把點u設定為走過` $\to$ `visited[1]=1`
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 | `1` |
| 2 | | 0 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 6 | | 7 | `1` |
</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 | `1` |
| 2 | | 0 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 6 | | 7 | `1` |
</div>
----
這樣就走完ㄌ
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; left: 0%; top:90%;">
| | | dis | visited |
| --- | --- | --- | --- |
| 1 | | 5 | `1` |
| 2 | | 0 | `1` |
| 3 | | 2 | `1` |
| 4 | | 1 | `1` |
| 5 | | 4 | `1` |
| 6 | | 7 | `1` |
</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)$
因為$V^2$太大，我們嘗試把$V^2$優化掉
----
目標 ： `選一個離起點最近並且沒有走過的點u`
代表我們需要選一個點u，他的dis[u]要最小，而且vis = 0
大家可以想一下要怎麼樣比$O(V)$還要快選到這個點$u$
----
我們可用到priority_queue，他可以在$O(\log_2 n)$的時間復雜度內找到最小/大的值
透過這個 $O(V * V)$ -> $O(V\log_2 V)$ ($10^{10}$ -> $1.6 \times 10^6$)
很明顯這樣複雜度就好了
----
總複雜度
1. 初始化 $\to$ $O(V)$
2. 選一個離起點最近並且沒有走過的點$u$ $\to$ $O(V \cdot logV)$
3. 把點$u$設定為走過 $\to$$O(V \cdot 1)$
4. 透過所有連接點$u$和$v$的邊，去鬆弛點$v$ $\to$ $O(E)$
總複雜度：$O(VlogV+E)$
----
若是邊權只有0或1，有沒有更好的優化方式？
----
使用deque取代priority_queue。
可以發現我們只要維持每次取出最小值
所以邊權為0我們就把他push_front()
邊權為1我們就把他push_back()
這樣可以保持deque內的單調性質
選一個離起點最近並且沒有走過的點的複雜度從 $O(logV)$ 再次降低到 $O(1)$
這個技巧以後應該還會提到 叫做 $0-1BFS$
----
## 實作
我們在priority_queue存入一個pair<int, int>
第一維存dis
第二維存點id
因為pair優先照第一維排序，所以取出來的會是dis最小的
```cpp
priority_queue<pii, vector<pii>, greater<pii>> pq;
```
----
範例code：
```cpp=
vector<pair<int, int>> E[V];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
vector<int> dis[N];
Q.emplace(0, 起點);
while(Q.size()) {
auto [du, u] = Q.top(); Q.pop(); // 取出當前最近的點
if(dis[u].size() >= 1) continue; // 這個等於已經vis過的點 （已經算出距離）
dis[u].push_back(du); // 算出距離
for(auto [v, w] : E[u]) Q.emplace(w + du, v);
}
```
----
0-1BFS
```cpp=
vector<pair<int, int>> E[V];
vector<int> dis[N];
deque<pair<int, int>> Q;
Q.emplace_front(0, 起點);
while(Q.size()) {
auto [du, u] = Q.front(); Q.pop_front(); // 取出當前最近的點
if(dis[u].size() >= 1) continue; // 這個等於已經vis過的點 （已經算出距離）
dis[u].push_back(du); // 算出距離
for(auto [v, w] : E[u]) {
if (w) Q.emplace_back(w + du, v);
else Q.emplace_front(w + du, v);
}
}
```
----
## 小限制
如果圖中有負權邊，Dijkstra這個演算法不能用
因為Dijkstra會取dis最小的點，在有負權邊的情況下會爛掉
----
起點為1的時候會爛掉
----
## 最短路徑樹
當你給定了一個起點，從這個起點走到任意的點的路徑會形成一棵樹(也有可能是多顆)
以下面的例子來說，最短路徑樹有兩顆
---
## 下課時間
---
## Bellman-Ford
----
## 想法
Bellman-Ford是以每一條邊去做鬆弛，能鬆弛就直接去做鬆弛，直到不能鬆弛為止。
----
不難發現由於一條最短路最多會經過$n-1$條邊，因此只要對每個邊鬆弛$n-1$次就好。
----
以每一條邊去做鬆弛
```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)$
----
## 負環
可以無限減少花費的一個環 ($1 \to 3 \to 2 \to 1$)
----
有負環的話 會發現可以無限進行鬆弛操作
----
## 判斷負環
若是第$n$輪鬆弛還有點被鬆弛到 代表這張圖存在負環
----
## 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
----
## 定義
dp[$k$][$i$][$j$] $\to$ 代表從 $i$ 到 $j$ 只經過 $1$ ~ $k$ 的最短距
----
## 初始化
dp[$0$][$i$][$i$] $\to$ 0
dp[$0$][$i$][$j$]
if : $i$ 到 $j$ 有邊 dp[$0$][$i$][$j$] $=$ 邊權
else : dp[$0$][$i$][$j$] = $\infty$
----
## 轉移
dp[$k$][$x$][$y$] = min(dp[$k-1$][$x$][$y$], dp[$k-1$][$x$][$k$] + dp[$k-1$][$k$][$y$])
----
## 實現
```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)$
時間複雜度：$O(N^3)$
----
## 空間優化
可以發現轉移的時候有一維是可以滾動掉的
dp[$k$][$i$][$j$] $\to$ dp[$i$][$j$]
所以空間複雜度可以優化到 $O(N^2)$
----
Floyd-warshall可以在時間複雜度$O(N^3)$、空間複雜度$O(N^2)$以內做完全點對最短路徑問題
基本上要做全點對最短路徑一定砸Floyd-warshall
---
來練習0.0
[題目連結](https://vjudge.net/contest/697920)
{"title":"Shortest Path","description":"Introduction to Competitive Programming2/27","contributors":"[{\"id\":\"3a4ab387-f23d-466f-a3db-98c85d8d5efb\",\"add\":11518,\"del\":10905},{\"id\":\"08326fa4-ca9b-4ca9-873e-239ebe76662c\",\"add\":138,\"del\":42}]"}