---
tags: 進階班
---
# 最短路徑 shortest path
## 甚麼是最短路徑？
給定一個帶權圖及點 `l, r`，求點 `l` 走到點 `r` 的最小路徑權重和。
設一圖：
其中要求第 $1$ 點和第 $3$ 點的最短路徑，那麼答案就是：
$3 + 1 = 4\Rightarrow 4$
## 演算法：發展期
`shortest path` 一開始時，大家想出的是複雜度較高的算法，但都是後來複雜度較低演算法的基礎。
其中一個大概念是鬆弛 (`Relaxation`)
設有一圖：
我們可以得知：從第 $2$ 點到第 $3$ 點，如果只走一條路，則長度為 $8$。
但若找到一點 $k$，使 $dis(2, k) + dis(k, 3) < dis(2, 3)$，則答案會縮小，更接近最短路徑解。如下圖例子：
此技巧即鬆弛，且我們能得知：$min(dis(2, 3))\leq 6$ (因為鬆弛是可以進行很多次的)
### Floyd-Warshall 演算法
這個演算法就是將所有點對其他點都鬆弛過，那麼找到的路徑解即最短路徑。
```cpp=
int n, rd, l, r, v;
cin >> n >> rd;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9));
for(int i = 0; i < rd; i++){
cin >> l >> r >> v;
dp[l][r] = dp[r][l] = v;
//每條路皆雙向
}
//以下即 Floyd-Warshall
for(int k = 1; i <= n; i++){
for(int i = 1; j <= n; j++){
for(int j = 1; k <= n; k++){
dp[i][j] = min(dp[i][k] + dp[k][j] , dp[i][j]);
//窮舉所有鬆弛可能
}
}
}
cin >> l >> r;
cout << dp[l][r];
```
偽代碼
```cpp=
FOR k <- 1 to N
FOR i <- 1 to N
FOR j <- 1 to N
dis(i, j) <- min(dis(i, k) + dis(k, j), dis(i, j))
```
`Time Complexity:` $O(N^3)$
為甚麼迴圈的順序是 `k, i, j` 呢？
看看以下的圖：
假設迴圈擺放是 `i, j, k`，那麼 `dp[i][j]` 只會遍歷「連續的 `k` 次」
而不管是第 $3,\;4,\;5$ 點都無法鬆弛 `dp[1][2]` (因為 `dp[1][2]` 是最先被鬆弛的)
這樣就會導致 `dp[1][2]` 有問題。
因此想法應該是對每個點窮舉所有 `dp[i][j]` 鬆弛。
優點：經過一次 `Floyd-Warshall` 後，所有兩點最短距離就都知道了！
### Bellman-Ford 演算法
由 `Floyd-Warshall` 程式碼可知它是對整個圖中的每一點鬆弛。
但我們可以先**得知起始點**，並對「邊」進行鬆弛。
$\Rightarrow$ 一次只能跑出一個點對所有點的最短路徑，`dp[i]` 代表一點 `u` 走到 `i` 點的最短距離
由於一條最短路最多會經過 $n - 1$ 條邊，因此只要對每個邊鬆弛 $n - 1$ 次就好。
因此又誕生一個演算法：`Bellman-Ford`
```cpp=
struct road{
int l, r, val;
};
int main(){
int n, e, l, r, v;
cin >> n >> e;
vector<int> dp(n + 1, 1e9);
vector<road> rd(e << 1);
for(int i = 0; i < e; i++){
cin >> l >> r >> v;
rd[i << 1] = {l, r, v};
rd[i << 1 | 1] = {r, l, v};
}
cin >> l >> r;
dp[l] = 0;
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < e * 2; j++){
dp[rd[j].r] = min(dp[rd[j].r], dp[rd[j].l] + rd[j].val);
}
}
for(auto & i : dp) cout << i << ' '; // l 到每個點的距離
return 0;
}
```
偽代碼
```cpp=
STRUCT edge{
point from, to
value val
}
//dis(k) <- the distance from st to k
dis(st) <- 0
dis(else) <- INF
//from -> to
FOR i <- 1 to N //repeat N times
FOR e <- all_edge
dis(e.to) <- min(dis(e.to), dis(e.from) + e.val)
```
而觀察以下圖：
從第 $2$ 點到第 $3$ 點的最短路徑是 $2$ 還是 $-1$ 還是 $-4$ ...呢？
由於這種圖(負環)沒有最短路徑，需排除。
而負環會鬆弛超過 $N - 1$ 次，因此可以在 `Bellman-Ford` 演算法結束後判斷。
```cpp=24
for(int j = 0; j < e * 2; j++){
if(dp[rd[j].r] > dp[rd[j].l] + rd[j].val) cout << "neg cycle\n";
}
```
`Time Complexity:` $O(NE)$
## 演算法：成熟期
這時，有比較快的演算法出現。
### SPFA (Shortest Path Faster Algorithm)
從 `Bellman-Ford` 可得知，它是對每個邊都鬆弛。
然而，在求兩點距離時，**一個點被鬆弛過，才可以去鬆弛其他點。**
而可鬆弛的點會從原點開始擴散。
這時實作及概念會有點像 `BFS`。
就是從起點 `i` 擴散，到達每一點 `k` 時一樣要判斷 `dis[k] = min(dis[j] + dis(j, k), dis[k])`
而因為它是 `Bellman-Ford` 演算法的優化版，因此它也可以檢查負環。
```cpp=
#define mem(x) memset(x, 0, sizeof(x))
struct road{
int r, val;
};
int main(){
int n, e, l, r, v;
cin >> n >> e;
vector<int> dp(n + 1, 1e9);
vector<road> rd[n + 1];
for(int i = 0; i < e; i++){
cin >> l >> r >> v;
rd[l].push_back({r, v});
rd[r].push_back({l, v});
}
cin >> l >> r;
dp[l] = 0;
queue<int> que;
que.push(l);
bool check[n + 1]; mem(check);
int cnt[n + 1]; mem(cnt);
while(!que.empty()){
int tmp = que.front(); que.pop();
check[tmp] = 0, cnt[tmp]++;
if(cnt[tmp] >= n) {cout << "neg cycle\n"; break;}
for(auto & i : rd[tmp]){
if(dp[i.r] > dp[tmp] + i.val){
dp[i.r] = dp[tmp] + i.val;
if(!check[i.r]) check[i.r] = 1, que.push(i.r);
}
}
}
for(auto & i : dp) cout << i << ' ';
return 0;
}
```
幾個實作上的新東西：
1. `check[]` 判斷點不在 `queue` 內才可以做 `BFS` (不然用 `queue` 裡的點做 `BFS` 就好)
2. `cnt[]` 判斷點被丟進 `queue` 幾次，用來檢查負環
3. `struct road` 剩下 `r, val`，因為 `l` 可以用 `vector` 的下標搞定
4. 一個點被鬆弛過，才可以去鬆弛其他點
`Time Complexity:` $O(NE)$ 但有很大的常數優化 (剪枝)
---
最後，還有一個幾乎是最優的演算法。
但它無法檢查負環，也不能解有負環的題目。
不過...要檢查負環的題目數量趨近於 $0$ :poop:
### Dijkstra 演算法
想法：從起點延伸出去的邊中，先把所有邊都丟進一個容器裡(權重設定為 `dis(start, i) + v`)，
再選出容器中權重最小的邊，把它接起來，此時權重即為連接到的 `j` 點權重。
接著以 `j` 為原點擴散，把連接到的邊丟進容器，重複動作直到連接至終點。
為了讓容器有「選出最小邊」的功能，因此選用 `priority_queue`
```cpp=
#define mem(x) memset(x, 0, sizeof(x))
struct road {
int r, val;
bool operator<(road rd) const {return val >= rd.val;} //pick the smallest
};
int main() {
int n, e, l, r, v;
cin >> n >> e;
vector<int> dis(n + 1, 1e9);
vector<road> rd[n + 1];
bool visited[n + 1]; mem(visited);
for(int i = 0; i < e; i++){
cin >> l >> r >> v;
rd[l].push_back({r, v});
rd[r].push_back({l, v});
}
priority_queue<road> pq;
cin >> l >> r;
int tmp = l;
dis[l] = 0; visited[l] = 1;
while(tmp != r){
for(auto & i : rd[tmp]) {
if(!visited[i.r])
pq.push({i.r, dis[tmp] + i.val});
}
road tp_rd;
while(visited[tmp]){
tp_rd = pq.top(), pq.pop();
tmp = tp_rd.r;
}
visited[tmp] = 1, dis[tmp] = tp_rd.val;
}
for(auto & i : dis) cout << i << ' ';
return 0;
}
```
```cpp=
dis(st) <- 0
dis(else) <- INF
min_dis() // get the min_dis val and position
min_dis() add (0, st)
WHILE min_dis() != empty
now_pos <- min_dis()
del min_dis()
IF is_vis(now_pos)
continue
dis(now_pos) <- now_pos.val
//vis = true
FOR e <- edge(now_pos) // the edges that is from now_pos
IF not_vis(e.to) :
min_dis() add (now_pos.val + e.val, e.to)
```
`Time Complexity:` $O(NlgE)$
## 題目練習：DanDanJudge
[a577. 避難所](http://203.64.191.163/ShowProblem?problemid=a577)
這題是「兩點最短路」的變化題，因為可能不只一個避難所。
可以把所有避難所的 `dis[i]` 都先設為 $0$，
而因為沒有負環，所以用 `dijkstra` 就好。
:::spoiler `code`
```cpp=
#include<bits/stdc++.h>
#define mem(x) memset(x, 0, sizeof(x))
#define LL long long
using namespace std;
struct road {
LL r, val;
bool operator<(road rd) const {return val >= rd.val;} //pick the smallest
};
int main() {
cin.tie(nullptr), ios_base::sync_with_stdio(false);
int n, m, k, r, lt, rt, v;
cin >> n >> m >> k >> r;
vector<LL> dis(n + 1, 1LL * 1e15);
vector<road> rd[n + 1];
bool visited[n + 1]; mem(visited);
for(int i = 0, root; i < k; i++)
cin >> root, dis[root] = 0, visited[root] = 1;
for(int i = 0; i < m; i++){
cin >> lt >> rt >> v;
rd[lt].push_back({rt, v});
rd[rt].push_back({lt, v});
}
int visit = n - k - r, tmp;
priority_queue<road> pq;
for(int i = 1; i <= n; i++){
if(visited[i]){
tmp = i;
for(auto & j : rd[i]){
if(!visited[j.r])
pq.push({j.r, j.val});
}
}
}
while(visit--){
for(auto & i : rd[tmp]) {
if(!visited[i.r])
pq.push({i.r, dis[tmp] + i.val});
}
road tmp_rd;
while(visited[tmp]){
tmp_rd = pq.top(), pq.pop();
tmp = tmp_rd.r;
}
visited[tmp] = 1, dis[tmp] = tmp_rd.val;
}
cout << dis[tmp] << '\n';
return 0;
}
```
:::
## 技術及經驗總結
其實...記 `dijkstra` 就好，因為其他真的太少用到了
有餘力再去記其他演算法
Sign in with Wallet
Connect another wallet