<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
#red{
color:red;
}
#gre{
color:green;
}
</style>
# Shortest Path
Introduction to Competitive Programming
2/22
----
- Single Source Shortest Paths
- Dijkstra
- Bellman-Ford
- SPFA
- All Pair Shortest Paths
- Floyd Warshall
----
## Single Source Shortest Paths
### 單源最短路徑
給定起點，求出起點到所有點的最短路徑
- Dijkstra
- Bellman-Ford
- SPFA
----
## All Pair Shortest Paths
### 全點對最短路徑
求出圖上所有點對的最短路徑
- Floyd Warshall
----
## 複習一下建圖
初始化 有 n 個點，編號為 0~n-1
```cpp=
int n;
vector<pair<int, int>> edge[MXN];
void init(int _n){
n = _n;
for(int i = 0; i < n ;i++){
edge[i].clear();
}
}
```
----
## 複習一下建圖
單向圖 (一條點 u 連向點 v 權重為 w 的邊)
```cpp=
void addEdge(int u, int v, int w){
edge[u].push_back({v, w});
}
```
雙向圖 (一條點 u 與點 v 連通權重為 w 的邊)
```cpp=
void addEdge(int u, int v, int w){
edge[u].push_back({v, w});
edge[v].push_back({u, w});
}
```
---
- Single Source Shortest Paths
- <span><!-- .element: class="fragment highlight-red" -->Dijkstra</span>
- Bellman-Ford
- SPFA
- All Pair Shortest Paths
- Floyd Warshall
----
## 想法
設 w[a][b] 為點 a 到點 b 的邊權重
先將所有點到起點的距離設為無限大 ( 用 dis 陣列紀錄 )
而且起點自己本身的距離設為 0
重複以下步驟，直到全部點都走過為止
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
----
## 鬆弛 (relaxation)
在計算最短路徑時，
已知從原點到點 $u$ 的最短路徑為 dis[$u$]，到點$v$的距離為 dis[$v$]
對於邊 $e(u, v)$，若我們可以從點 $u$ 出發經過 $e$ 更新點 $v$ 的最短路徑
則我們稱透過 $e$ 進行了一次鬆弛操作
也就是我們用 dis[$u$]+$e$ 使得 dis[$v$] 更小
以上圖為例，我們可以透過邊 (2, 3)，去鬆弛從起點到點3的最短路徑
----
## code
透過點 $u$ 經過一條權重為 $w$ 的邊，去鬆弛點 $v$
```cpp=
void relaxation(int u, int v, int w){
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
}
}
```
----
## dijkstra
1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 65%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | false |
| 2 | INF | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | INF | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 65%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | <span id="red">true</span> |
| 2 | INF | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | INF | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | INF | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | ~~INF~~ $\to$ <span id="gre">10</span> | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | ~~INF~~ $\to$ <span id="gre">5</span> | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | ~~INF~~ $\to$ <span id="gre">3</span> | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |
</div>
----
## dijkstra
1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | 3 | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | 3 | <span id="red">true</span> |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | 3 | true |
| 4 | ~~INF~~ $\to$ <span id="gre">6</span> | false |
| 5 | INF | false |
| 6 | 10 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | <span id="red">true</span> |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | INF | false |
| 6 | 10 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | INF | false |
| 6 | ~~10~~ $\to$ <span id="gre">7</span> | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | ~~INF~~ $\to$ <span id="gre">10</span> | false |
| 6 | 7 | false |
</div>
----
## dijkstra
1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | 10 | false |
| 6 | 7 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | <span id="red">true</span> |
| 5 | 10 | false |
| 6 | 7 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | ~~10~~ $\to$ <span id="gre">9</span> | false |
| 6 | 7 | false |
</div>
----
## dijkstra
1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 | false |
| 6 | 7 | false |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 | false |
| 6 | 7 | <span id="red">true</span> |
</div>
----
## dijkstra
1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 | false |
| 6 | 7 | true |
</div>
----
## dijkstra
1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 60%;">
| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 |<span id="red">true</span> |
| 6 | 7 | true |
</div>
----
## 最短路徑表格
<div style="position: absolute; right: 75%; top:90%;">
| node | dis[i] |
| ------ | ------ |
| 1 | 0 |
| 2 | 5 |
| 3 | 3 |
| 4 | 6 |
| 5 | 9 |
| 6 | 7 |
</div>
<div style="position: absolute; right: 20%; top:90%;">
</div>
----
## 性質
每條最短路徑都是其他最短路徑所延伸的，把全部最短路徑畫出來
最後會形成一顆最短路徑樹 (可能不只一種)
<div style="position: absolute; right: 0%; top:90%;">
</div>
<div style="position: absolute; right: 50%; top:200%;">
$\to$
</div>
<div style="position: absolute; right: 60%; top:90%;">
</div>
----
## 實作
0. 初始化
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
----
## 初始化
將除了起點的點距離設為無限大
而無限大通常設為一個比可能的最短路徑還大的權重
```cpp=
#define INF 1e18
for(int i=0;i<n;i++){
if(i == start)
dis[i] = 0;
else
dis[i] = INF;
}
```
----
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
```cpp [|2-7|8-9|10|11-16]
while(1){
int ind = -1, mx = INF;
for(int i = 0; i < n; i++){ // 1. 選從還沒走過的點中，離起點最近的點
if(!vis[i] && dis[i] < mx){
ind = i, mx = dis[i];
}
}
if(ind == -1) // 如果全部點都走過則結束演算法
break;
vis[ind] = 1; // 2. 將此點設定為走過
for(int i = 0; i < edge[ind].size(); i++){ // 3. 窮舉此點所有連到的點，進行鬆弛
int u = edge[ind].to, w = edge[ind].weight;
if(dis[u] > dis[ind] + w){
dis[u] = dis[ind] + w;
}
}
}
```
----
## 複雜度
根據演算法
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
每個點會走過一次，會花 $O(N)$ 時間找離起點最近的點
接著再跑過 $M$ 條邊 (每條邊最多被跑過一次)
因此複雜度為 $O(N^2 + M)$
----
來看看題目的範圍大小
[CSES : Shortest Routes I
](https://cses.fi/problemset/task/1671)
算起來約為 $10^{10}$
怎麼看都會 `TLE`
----
## 優化
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛
每次都是從還沒走過的點中選距離最小的
則我們可以用 pririty_queue 存起來，每次取 top
當有更新邊的時候，則丟進去 priority_queue 裡面
----
## 實作
priority_queue 裡面存有被鬆弛過的點
一開始將原點丟進去，接著一直鬆弛直到沒有邊可以鬆弛為止
----
## 範例程式碼(求出 s 到 t 的最短路徑)
```cpp=
#define ll long long
int n, m, s, t;
ll dis[MXN];
vector<pair<int, ll>> edge[MXN];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq; // 為了方便實作，用pair包起來會先比較距離大小
void init(){
cin >> n >> m >> s >> t;
for(int i = 0, u, v, w; i < m; i++){
cin >> u >> v >> w;
edge[u].emplace_back(v, w);
}
}
long long dijkstra(){ //求出 s 到 t 的最短路徑
memset(dis, 0x3f, sizeof(dis)); // 初始化所有距離為無限大
dis[s] = 0; // 起點距離為 0
pq.push(make_pair(dis[s], s)); // 從起點出發
while(!pq.empty()){
auto [d, u] = pq.top(); pq.pop();
if(vis[u]) continue; // 確保每個點最多只被走過一遍
vis[u] = 1;
for(int i = 0; i < edge[u].size(); i++){ // 窮舉此點所有連到的點
int v = edge[u][i].to, w = edge[u][i].weight;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w; // 鬆弛
pq.push(make_pair(dis[v], v)); // 如果有更新距離，則丟進 priority_queue
}
}
}
return dis[t];
}
int main(){
init();
cout << dijkstra() << endl;
}
```
----
## 複雜度
總共 $N$ 個點，每個點只走過一遍
用 priority_queue 優化 $O(N)\to O(\log N)$
每條邊被遍歷過一次 $O(M)$
總複雜度 $O(M + M\log N)$
----
## 限制
dijkstra 演算法只能跑邊權重 $\ge 0$ 的圖
因為核心概念：每次都跑還沒走過的點中最近的
所以如果出現負權邊，則會違反以上條件
----
以上圖為例先用點 1 更新點 2，距離為 3
在更新點 3 時，會發現點3的距離變成 -2，比點 1、2 都還要離起點更近，則違反演算法
----
因此在做 dijkstra 時，要確保邊權重沒有負的，否則正確性會爛掉
----
## Another Problem
NCPC 2021 final
----
## Target
maximum number of unvisited spot along shortest path
- Time Limit: 2 second
- testcase $\le 16$
- $N, M\le 10^5$
dijkstra $\to O(T \cdot M \log N)\approx 2.6\cdot 10^7$
----
## Contest Result
problem J
Accepted: 34/109 teams
First Accepted: 21 min
<div style="position: absolute; right: 20%;top: -8%;">
</div>
----
classic dijkstra
```cpp
long long dis[N];
```
this problem
```cpp
pair<long long, int> dis[N]; //shorter path then more unvisited spot
```
----
## Number of Shortest Path ([UVa 10917](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1858))
Given a directed positive weighted graph, count number of shortest path from vertex $S$ to $T$ module 2147483647
- $1\le N, M\le 2\cdot 10^5$
from 1 to 5: {1, 2, 3, 4, 5}, {1, 2, 4, 5}, {1, 5} $\to$ 3 ways
----
### The distance of each vertex
----
### The edge on the shortest path (red edge)
----
從 1 到 5 的最短路徑個數為
所有到 5 的邊中為最短路徑上的邊的來源點
到點 1 的最短路徑數量 + 到點 4 的最短路徑數量
----
會發現所有最短路徑上的邊連成的圖
是一張有向無環圖 $\to$ DP on DAG
----
```cpp=
bool vis[N];
ll dp[N];
ll DP(int x){
if(vis[x]) return dp[x];
vis[x] = 1;
if(x == startPoint){
dp[x] = 1;
return dp[x];
}
for(auto [from, len] : from[x]){
if(dis[from] + len == dis[x]){
dp[x] += DP(from);
dp[x] %= MOD;
}
}
return dp[x];
}
int main(){
dijkstra();
cout << DP(endPoint) << endl;
}
```
---
- Single Source Shortest Paths
- Dijkstra
- <span><!-- .element: class="fragment highlight-red" -->Bellman-Ford</span>
- SPFA
- All Pair Shortest Paths
- Floyd Warshall
----
## 想法
類似 dijkstra
每次嘗試邊集合去鬆弛最短路徑
直到沒有點可以進行鬆弛為止
<!-- 對圖上的兩個點 A、B，如果可以找到一個邊g[a][b] -->
----
## 嘗試鬆弛
```cpp=
for(int i = 0; i < m; i++){ // 對於所有邊都嘗試鬆弛
if(dis[ edge[i].to ] > dis[ edge[i].from ] + edge[i].weight){
dis[ edge[i].to ] = dis[ edge[i].from ] + edge[i].weight;
}
}
```
而最差情況下我們需要鬆弛幾輪才能找到全部點的最短路徑?
----
$N$ 個點，最差的情況下需要 $N-1$ 輪鬆弛
每輪鬆弛都只更新到一個點，而最遠的情況下連 $N-1$ 條邊
<span>  <!-- .element: class="fragment" data-fragment-index="1" --></span>
<span>  <!-- .element: class="fragment" data-fragment-index="2" --></span>
<span>  <!-- .element: class="fragment" data-fragment-index="3" --></span>
----
## 複雜度
每輪鬆弛 $O(M)$
最多鬆弛 $N-1$ 輪
因此為 $O(NM)$
```cpp=
for(int j = 0; j < n-1; j++){
for(int i = 0; i < m; i++){ // 對於所有邊都嘗試鬆弛
if(dis[ edge[i].to ] > dis[ edge[i].from ] + edge[i].weight){
dis[ edge[i].to ] = dis[ edge[i].from ] + edge[i].weight;
}
}
}
```
----
## 負環
假設 1 為源點，要求出點 1 到所有點的最短路徑
在有負環 (234) 的情況下，找不到最短路徑
如果用 Bellman-ford，則永遠更新不完
----
## 偵測負環
因此假設我們要找一張圖有沒有負環，則可以使用 Bellman-ford
在沒有負環的情況下，我們最多只需要跑 $n-1$ 次後，則找不到點去鬆弛
因此跑完 $n-1$ 次之後，我們再多跑一次，只要有點可以鬆弛，則代表此圖有負環
---
- Single Source Shortest Paths
- Dijkstra
- Bellman-Ford
- <span><!-- .element: class="fragment highlight-red" -->SPFA</span>
- All Pair Shortest Paths
- Floyd Warshall
----
## SPFA(Shortest Path Faster Algorithm)
Bellman-ford 優化版
----
在Bellman-ford的演算法中，每次鬆弛都會跑過全部的邊
但實際上很多次都是非必要的
假設有一條邊 $x$ 連到 $y$，在點 $x$ 都還沒被鬆弛的情況下，則還沒必要用這條邊來鬆弛 $y$
因此我們可以用一個 queue 來儲存哪些點被鬆弛過，只跑 queue 裡面的點就好
----
寫起來類似 dijkstra
```cpp=
queue<int> que;
que.push(start); // 起點一開始為 0 放進去鬆弛其他點
while(!que.empty()){
int u = que.front(); que.pop();
for(int i = 0; i < edge[u].size(); i++){
if(dis[ edge[u][i].to ] > dis[u] + edge[u][i].weight){
dis[ edge[u][i].to ] = dis[u] + edge[u][i].weight;
que.push(edge[u][i].to); // 如果被鬆弛，則可以拿來鬆弛其他點
}
}
}
```
----
接著如果一個點已經在 queue 裡面了，則不需要重複 push 進去
因此我們可以用一個 bool 陣列紀錄是否已經在 queue 裡面
```cpp=
bool inque[N]; // 紀錄是否已經在 queue 裡面
queue<int> que;
que.push(start);
while(!que.empty()){
int u = que.front(); que.pop();
inque[u] = 0; // 從 queue 拿出來設成 0
for(int i = 0; i < edge[u].size(); i++){
int v = edge[u][i].to, w = edge[u][i].weight;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w; // 鬆弛
if(!inque[v]){
que.push(v);
inque[v] = 1; // 放進 queue 裡面設成 1
}
}
}
}
```
----
## 利用 SPFA 判斷負環
原本 Bellman-ford 判斷負環的方法是先跑 $N-1$ 輪鬆弛
第 $N$ 輪時檢查是否有點能在被鬆弛
但現在改為用 queue 之後無法判斷
因此我們要設一個 len 陣列，紀錄每個點從起點開始是第幾輪被更新到
超過 $N-1$ 輪還可以更新，則代表有負環的出現
<div style="position: absolute; right: 80%;">
</div>
<div style="position: absolute; right: 40%;">
</div>
----
## 程式碼
```cpp=
int len[N]; // 紀錄每個點是第幾輪被鬆弛到
bool inque[N];
queue<int> que;
que.push(start);
while(!que.empty()){
int u = que.front(); que.pop();
if(len[u] > n-1) return -1; // 超過 n-1 輪，找到負環
inque[u] = 0;
for(int i = 0; i < edge[u].size(); i++){
int v = edge[u][i].to, w = edge[u][i].weight;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
len[v] = len[u] + 1; // 從來的點 +1輪被鬆弛到
if(!inque[v]){ // 如果本來沒在 queue 裡就丟進去
que.push(v);
inque[v] = 1; // 紀錄是否在 queue 裡
}
}
}
}
```
----
## 優化
使用 deque 取代 queue
原本：queue 的 front 取出來，改成：deque 從頭尾判斷哪個的距離比較小
```
if dis[ deq.front ] <= dis[ deq.back ]
pop front
else
pop back
```
想法：由於要找負環，所以順序從距離越小越好
----
## 程式碼
```cpp=
deque<int> deq; // 改成 deque
deq.push_back(start);
while(!que.empty()){
// 取頭尾離起點距離較小的點
int u = (dis[deq.front()] < dis[deq.back()] ? deq.front():deq.back());
dis[deq.front()] < dis[deq.back()] ? deq.pop_front():deq.pop_back();
if(len[u] > n-1) return -1;
inque[u] = 0;
for(int i = 0; i < edge[u].size(); i++){
int v = edge[u][i].to, w = edge[u][i].weight;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
len[v] = len[u] + 1;
if(!inque[v]){
inque[v] = 1;
que.push(v);
}
}
}
}
```
----
## 複雜度
號稱 $O(N)$，在一般 random 產出來的圖跑十分的快
但
上面的優化大部分都是想法或常數上的優化
實際上最差的情況下複雜度依舊是 $O(NM)$
並且常數巨大在最差的情況下會跑得比 Bellman-ford 慢
~~不過台灣站的測資大部分很爛~~
----
## Problem
NCPC 2019 final
----
## Target
Ask is there any negative cycle path in the graph?
- testcase $\le 40$
- $N\le 100$
- $M\le ?\to N^2$
SPFA $\to O(T\cdot NM) = 4\cdot 10^7$
----
## Contest Result
AC in Contest: 38/92 teams
First Accepted: 8 mins
<div style="position: absolute; right: 20%;top: -8%;">
</div>
---
- Single Source Shortest Paths
- Dijkstra
- Bellman-Ford
- SPFA
- <span><!-- .element: class="fragment highlight-red" -->All Pair Shortest Paths</span>
- <span><!-- .element: class="fragment highlight-red" -->Floyd Warshall</span>
----
## 想法
如果要求一個點對的最短路徑，可能會經過 $V_1$、$V_2$ ...這些點
我們稱 $V_i$ 這些點為中繼點
只要窮舉每一個中繼點去更新最短路徑，
就可以更新到全部的最短路徑。
----
## 例子
設 `dis[i][j]` 為從點 `i` 到點 `j` 的距離
下圖為例，我們可以知道 `dis[1][2]` 為 `7`，`dis[2][3]` 為 `2`
如果我們想算 `dis[1][3]` 則可以透過中繼點 `2` 來去更新 `1` 到 `3` 的最短路徑
`dis[1][3] = min( dis[1][3], dis[1][2] + dis[2][3]);`
----
以此類推，想算出 `dis[1][4]`
則可以透過點 `3` 來更新
`dis[1][4] = min( dis[1][4], dis[1][3] + dis[3][4]);`
----
依序加一個點當中繼點
接著窮舉所有點對 `(i, j)`，計算 `dis[i][j]` 從 `i` 出發經過中繼點在到 `j` 會不會更短
```cpp=
int dis[N][N];
for(int k = 0; k < n; k++){ // 窮舉中繼點 k
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){ // 窮舉點對 (i, j)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}
}
}
```
----
## 初始化
先將所有點對距離設為無限大，除了自己到自己距離為 `0`
```cpp=
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i != j)
dis[i][j] = INF;
else
dis[i][j] = 0;
}
}
```
對於給定的邊 `(u, v, w)`，更新 `dis[u][v] = w`
```cpp=
cin>> u >> v >> w;
dis[u][v] = min(dis[u][v], w);
```
----
## Complexity
Time Complexity： 3 loops $\to O(N^3)$
Space Complexity： 2D array $\to O(N^2)$
Actually, even if $N$ up to 1000, it can be passed within 1 second!
----
## Problem
NCPC 2019 final
Check Negative Cycle
----
如果存在負環，則繞一圈之後回到自己距離會變更短
----
## Floyd Warshall
dis[u][u] 一開始初始化成 0
如果存在負環，則跑完最短路徑後 dis[u][u] 會 < 0
----
$testcase\le 40$
$n\le 100$
$O(T\cdot N^3) = 4\cdot 10^7\to AC !$
----
## Problem
2020 NCPC preliminary
----
## Target
Given $N\times N$ all pairs shortest path.
There are $K$ operation, each operation update road length
between $u$ and $v$ to $w$.
After each operation print number of pair that reduced shortest path.
- testcase $\le 10$
- $N\le 1000$
- $K\le 50$
----
## Contest Result
problem E
Accpted: only 2/168 teams AC in contest
First Accpted: 142 mins
----
每次有一條邊更新，有影響的最短路有哪些?
----
每次有一條邊更新，有影響的最短路有哪些?
有被影響的只有通過這條新邊的點對 !
----
分別窮舉以這兩個端點為中繼點的最短路徑
判斷是否有更新
----
每次更新 $O(N^2)$，總共 $K$ 筆更新
- testcase $\le 10$
- $N\le 1000$
- $K\le 50$
複雜度 $O(T\cdot N^2K)$ = 5e8
2 second can AC
----
```cpp=
void update(int u, int v, int k){
dis[u][v] = dis[v][u] = min(dis[v][u], k);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
dis[i][j] = min(dis[i][j], dis[i][v] + dis[v][j]); // update with v
dis[i][j] = min(dis[i][j], dis[i][u] + dis[u][j]); // update with u
}
}
}
```
---
### Single Source Shortest Path
| Algorithm | Time Complexity |
| -------- | -------- |
| Dijkstra | $O(V^2)$ |
| Dijkstra+PQ | $O(E\log V)$ |
| Bellman Ford | $O(VE)$ |
| SPFA | $O(VE)$ |
### All Pair Shortest Path
| Algorithm | Time Complexity |
| -------- | -------- |
| Floyd Warshall | $O(V^3)$ |
----
## Homework
deadline: 3/1
link: https://vjudge.net/contest/543564
{"metaMigratedAt":"2023-06-17T21:02:15.763Z","metaMigratedFrom":"YAML","title":"Shortest Path","breaks":true,"slideOptions":"{\"transition\":\"fade;\"}","contributors":"[{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":26646,\"del\":1481}]"}