<style>
.reveal .slides {
text-align: left;
font-size:35px;
}
</style>
# Shortest Path最短路徑
Introduction to Competitive Programming
2/16
---
### 什麼是最短路徑?
通常會有一張圖，要你算從起點$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>
----
## 鄰接矩陣--存圖
- 有向
```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;
}
```
----
## 鄰接串列
<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$
----
## 什麼是鬆弛
若圖中存在2個點$u$,$v$，並且存在一個連接$u,v$的邊，邊權為$w$，用dis[$u$]+$w$去取代dis[$v$]，這種技巧就叫鬆弛
----
假設你要算dis(2,3)，也就是2走到3的最短路徑
你走下面紅色那條邊之後，dis(2,3)會等於5
----
一樣你也可以走上面，先走到1，使得dis(2,1)=1
----
那再來你會發現你可以走右邊那條邊從1走到3
顯然上面的路徑權重比下面的還要少
所以要用dis(2,1)+3取代掉dis(2,3)
----
所以鬆弛會寫成像這樣
若「起點到u的最短距離」加上「u到v這條邊的權重」小於「起點到v的最短距離」就更新答案
```cpp!
void relax(int u,int v,int w){//w是邊權權重
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
}
}
```
----
學會鬆弛之後我們就可以看看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$太大，所以我們可以想辦法壓掉第二個步驟的複雜度
----
2. `選一個離起點最近並且沒有走過的點u`
你會發現你是要選一個點$u$，且dis[$u$]盡可能越小越好
大家可以想一下要怎麼樣比$O(V)$還要快選到這個點$u$
----
可以搭配priority_queue這個STL工具來用
你可以把每個有被鬆弛過的點x套成一個pair，(dis[x],x)丟進priority_queue裡面，裡面會按照dis去做排序
他可以幫你用$O(logV)$的時間知道哪個$u$的dis[$u$]是最小的
----
這時候的複雜度就會變成這樣
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)$
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(VlogV+E)$
----
## 小限制
如果圖中有負權邊，Dijkstra這個演算法不能用
因為Dijkstra會取dis最小的點，在有負權邊的情況下會爛掉
----
假設其他點都已經跑完了，剩下點6要跑一次
他可以用最下方權重為-10的邊去更新2
之後甚至也可以用點2再重新更新點4，因此這個演算法會爛掉
----
## 最短路徑樹
當你給定了一個起點，從這個起點走到任意的點的路徑會形成一棵樹(也有可能是多顆)
以下面的例子來說，最短路徑樹有兩顆
---
## 下課時間 好好消化剛剛剛教的內容
---
## 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)$
----
可以知道在進行$n-1$次對全部的邊做鬆弛之後會出現最短路徑，那如果是這張圖呢
----
以下是進行$n-1$次鬆弛的過程，你會發現在有負環的情況下他會爛掉
----
## 判斷負環
因此你可以考慮在第n次做一次鬆弛，如果有點被鬆弛到，代表這張圖存在負環
---
## Floyd-warshall
----
## 想法
對於一個點對(i,j)，我要找i走到j的最短路徑，可能會存在一個中繼點k。
這時候從i走到k加上k走到j的路徑可能會更短
因此這時候窮舉每個點k當作中繼點去更新答案
就可以更新所有最短路徑
----
`dis[i][j]`指的是從i走到j的最短路徑
`dis[1][3]`就代表從1走到3的最短路徑，一開始可能是無限大
可以找到一個中繼點2，這時候`dis[1][2]=1`且`dis[2][3]=5`，相加起來比`dis[1][3]`小
因此可以用來更新`dis[1][3]`
----
## 初始化和讀邊
- 自己到自己的距離為0，否則為INF
- 有一個有向邊為u走到v，權重為w，更新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]=1e18;
}
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
---
來練習8
[題目連結](https://vjudge.net/contest/603684#overview)
{"title":"Shortest Path","description":"Introduction to Competitive Programming2/16","contributors":"[{\"id\":\"08326fa4-ca9b-4ca9-873e-239ebe76662c\",\"add\":20641,\"del\":914},{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":1,\"del\":1},{\"id\":\"f252a272-5088-4254-be0e-814b97d3ed17\",\"add\":8,\"del\":8}]"}