# 求有權圖最短路徑 (Dijkstra's, Bellman-Ford, Floyd Warshall)
## Dijkstra's 演算法
* 介紹影片：https://www.youtube.com/watch?v=JLARzu7coEs
---
### 解釋：
:::warning
* 假設你有一個有權圖，叫你求一點到其他點的最短距離
* **very important: 權重不能有負的，不然就要用bellmen-ford**
* **只能求一點到其他點的最段路徑，否則就要用Floyd-Warshall**
:::
1. 將1到n的距離設成dist[n]，並將dist全部設成無限 (dist[1]=0)
* 目標：從目前dist最小的點，不斷更新他附近(沒走過)的點，並且將可更新的點存到
一個將 **距離由小到大** 的priority_queue (來處存dist最小的點)
* pq裡有可能有重複的點，則如果此點已經經過的話，則直接跳過
(因為比較小的距離之前就處裡過了)
* 若pq是空的就停掉
* (走過的點為綠色，正在更新的點為紅色，無法更新為紫色)
2. A連接B和C，可將dist[2]更新為4，dist[3]更新為8(4<inf, 8<inf)
並將B,C點丟到pq
3. B在pq最上層，所以對B做一樣的事
(因為C的8小於4+11，所以不用更新，也不用加到pq)
4. C在pq的最上方
5. F在pq的最上方
6. I在pq的最上方
7. D在pq的最上方
8. E在pq的最上方
9. H在pq的最上方
10. J在pq的最上方
* 答案就會是dist[n]
---
### 題目：
#### CSES - Shortest Routes I
> https://cses.fi/problemset/task/1671
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define maxn 100005
#define inf LLONG_MAX
#define int long long
using namespace std;
int n, m, dist[maxn]; vector<pair<int, int>> f[maxn]; bool vis[maxn];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
//f[i]存{j, i到j的距離}
//pq存{0到i到距離, i}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i=1; i<=m; ++i){
int a, b, c; cin >> a >> b >> c;
f[a].push_back({b, c});
}
for (int i=1; i<=n; ++i) dist[i] = inf;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()){
int p = pq.top().second; pq.pop(); //我們只需要pq最上面的點，距離是用來sort的
if (vis[p] == 1) continue;
//因為有可能有重複的點被放到pq，我們只需要處裡距離最小的，
//且pq的距離是由小排到大的，所以我們若造訪過就不用更新旁邊的了
vis[p] = 1; //設為造訪過
for (int i=0; i<f[p].size(); ++i){
int v=f[p][i].first; //要更新的點
int d=f[p][i].second; //現在點到要更新的點的距離
//若沒有參訪過，且新的距離小於原本的
if (vis[v] == 0 && dist[p]+d < dist[v]){
dist[v] = dist[p]+d; //更新dist
pq.push({dist[v], v}); //推進pq
}
}
}
for (int i=1; i<=n; ++i){
if (i==n) cout << dist[n] << endl;
else cout << dist[i] << " ";
}
}
```
---
#### 求路徑：
* 只要更新dist[i]同時，存到i點過來的點，最後從最後一點找回第一點就好了
(剛剛的程式)
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define maxn 100005
#define inf LLONG_MAX
#define int long long
using namespace std;
int n, m, dist[maxn], path[maxn]; vector<pair<int, int>> f[maxn]; bool vis[maxn]; vector<int> final_path;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i=1; i<=m; ++i){
int a, b, c; cin >> a >> b >> c;
f[a].push_back({b, c});
}
for (int i=1; i<=n; ++i) dist[i] = inf;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()){
int p = pq.top().second; pq.pop();
if (vis[p] == 1) continue;
vis[p] = 1; path[1] = 0;
for (int i=0; i<f[p].size(); ++i){
int v=f[p][i].first;
int d=f[p][i].second;
if (vis[v] == 0 && dist[p]+d < dist[v]){
dist[v] = dist[p]+d;
path[v] = p; //加這一行
pq.push({dist[v], v});
}
}
}
//輸出1到n點最短距離和路徑
cout << dist[n] << endl;
int x=n; //從n往回找
while (x != 0){ //path[1] = 0
final_path.push_back(x);
x = path[x];
}
//反向的輸出
for (int i=final_path.size()-1; i>=0; --i){
if (i==0) cout << final_path[i] << endl;
else cout << final_path[i] << " ";
}
}
```
---
#### E - Rush Hour 2
> https://atcoder.jp/contests/abc204/tasks/abc204_e
:::info
## 求等待時間的最佳值：
假設我們從出發點到一點的時間為 $t+a+C~i~+\lfloor \frac{D~i~}{t+1+a}\ \rfloor$
t = 前面花的時間
a = 等待時間 (要求最佳值的)
### 我們要求的就是 上述函式 的min值
---
1.先把常數拿掉
$a+\lfloor \frac{D~i~}{t+1+a}\ \rfloor$
2.floor拿掉(之後處理)，讓函式變連續的
$a+ \frac{D~i~}{t+1+a}$
3.微分求極植
$f(a) = a+ \frac{D~i~}{t+1+a}$
$f(a)' = 1- \frac{D~i~}{(t+1+a)^2}$
$let\ f(a)' = 0$
$\frac{D~i~}{(t+1+a)^2} = 1$
$a = \sqrt{D~i~}-t-1$
---
### 得出解果：
$a = \sqrt{D~i~}-t-1$ 時，時間會是最小的。
:::
:::spoiler 為什麼要微分，power rule，加法律
### 微分?
因為我們這一題是要找極值，並且$f(a)$微之後只有一個最低點 (凸的)，
而導數有點像找$f(a)$每一點的斜率，所以$f(a)'$為0時就是我們要找的答案。
---
### power rule:
$let\ f(x) = x^{n} + 2x^{n-1}$
$then\ f(x)' = nx^{n-1} + 2(n-1)x^{n-2}$
---
### 加法律：
$let\ h(x) = f(x) + g(x)$
$then\ h(x)' = f(x)' + g(x)'$
---
### 剩下自己看lol：
https://m.gamer.com.tw/home/creationDetail.php?sn=4950044
:::
:::success
## 微分小教室：連鎖律
* 假設我們有一個$f(g(x))$要對$x$微分，則先將$f(g(x))$對$g(x)$微分，再將$g(x)$對$x$微分，最後再相乘，就會是答案了：
## $\frac{df(g(x))}{dx} = \frac{df(g(x))}{dg(x)} * \frac{dg(x)}{dx}$
* 以我們上面題目舉例子：
原式：
$f(a) = a+ \frac{D~i~}{t+1+a}$
標示成這樣比較好看：
$f(a) = a+ D~i~*(t+1+a)^{-1}$
先微a：(加法律)
$f(a)' = 1+ \frac{d(D~i~*(t+1+a)^{-1})}{dx}$
再微後面的：
$f(a)' = 1+ -D~i~*(t+1+a)^{-2} * 1$
最後得到答案：
$f(a)' = 1- \frac{D~i~}{(t+1+a)^2}$
:::
```cpp
#include <bits/stdc++.h>
#define maxn 100005
#define inf LLONG_MAX
#define int long long
#define double long double
#define endl '\n'
using namespace std;
struct edge{
int v, w, d;
} temp;
int n, m, dist[maxn]; vector<edge> e[maxn]; bool vis[maxn];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=1; i<=m; ++i){
int a, b, c, d; cin >> a >> b >> c >> d;
e[a].push_back({b, c, d});
e[b].push_back({a, c, d});
}
for (int i=1; i<=n; ++i) dist[i] = inf;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()){
int v = pq.top().second; pq.pop();
if (vis[v]) continue;
vis[v] = 1;
for (edge k:e[v]){
int u = k.v, c = k.w, d = k.d, floora = inf;
if (vis[u]) continue;
double a = sqrt(d)-1;
if (a<dist[v]) floora = dist[v]+c+ d/(dist[v]+1);
else{
for (int i=a-5; i<=a+5; ++i){
if (i>=dist[v]) floora = min(floora, i+c+ d/(i+1) );
}
}
if (dist[u] > floora){
dist[u] = floora;
pq.push({floora, u});
}
}
}
if (dist[n] == inf) cout << -1 << endl;
else cout << dist[n] << endl;
}
```
#### TIOJ 2379
> https://tioj.ck.tp.edu.tw/problems/2379
* 太難了 我放棄 :(
* 會的教我一下 謝謝 :)
---
## Bellmam-Ford 演算法
### 解說：
* 最短路徑所經過的邊數，最多為 V-1 條
* 並且重複 V-1 次，每次將全部的邊兩點去更新
* (若這次更新沒有任何點被更新，則也代表結束)
:::success
偵測負環：
若更新到第 V 次的時候，卻還是有被更新的話，那就代表有負環
:::
---
### 題目：
#### CSES - High Score
> https://cses.fi/problemset/task/1673
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define maxn 5005
#define int long long
#define inf 1e18
using namespace std;
struct edge{
int u, v, w;
};
int n, m, dist[maxn]; vector<edge> e; bool flag, nag;
vector<int> f[maxn], nedge; bool vis[maxn];
bool dfs(int x){
if (x == n) return true;
vis[x] = 1;
for (int i:f[x]){
if (vis[i]) continue;
if (dfs(i)) return true;
}
return false;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=1; i<=m; ++i){
int a, b, c; cin >> a >> b >> c;
e.push_back({a, b, -c});
//要找最高的距離，則將輸入變成相反數，找最小的就是答案了
f[a].push_back(b);
}
for (int i=1; i<=n; ++i) dist[i] = inf;
dist[1] = 0;
for (int i=1; i<=n; ++i){
flag = false;
for (int j=0; j<m; ++j){
if (dist[e[j].u] == inf) continue;
if (dist[e[j].u] + e[j].w < dist[e[j].v]){
flag = true;
dist[e[j].v] = dist[e[j].u] + e[j].w;
if (i==n) nedge.push_back(e[j].v);
}
}
if (!flag) break;
if (flag && i==n) nag = true;
}
if (!nag) cout << -dist[n] << endl;
else{
//dfs to check if negative round connects to n
bool found=false;
for (int i:nedge){
if (dfs(i)){
found = true;
break;
}
}
if (found) cout << -1 << endl;
else cout << -dist[n] << endl;
}
}
```
---
#### CSES - Cycle Finding
> https://cses.fi/problemset/task/1673
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define maxn 2505
#define inf 1e18
#define int long long
using namespace std;
struct coord{
int u, v, d;
};
int n, m, dist[maxn], w[maxn], x; vector<coord> e; bool found;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=1; i<=m; ++i){
int a, b, c; cin >> a >> b >> c;
e.push_back({a, b, c});
}
for (int k=1; k<=n; ++k){
for (int i=1; i<=n; ++i) dist[i] = inf;
dist[k] = 0;
for (int i=1; i<=n; ++i){
bool flag = false;
for (int j=0; j<m; ++j){
int u = e[j].u, v = e[j].v, d = e[j].d;
if (dist[u] + d < dist[v]){
flag = true;
dist[v] = dist[u] + d;
w[v] = u;
if (i==n) x = v;
}
}
if (!flag) break;
if (i==n && flag) found = true;
}
if (found) break;
}
if (found){
cout << "YES" << endl;
for (int i=1; i<=n; ++i) x = w[x];
//make x go inside the cycle
vector<int> cycle; int v = w[x];
cycle.push_back(x);
while (v != x){
cycle.push_back(v);
v = w[v];
}
cycle.push_back(x);
reverse(cycle.begin(), cycle.end());
for (int i=0; i<cycle.size(); ++i){
if (i==cycle.size()-1) cout << cycle[i] << endl;
else cout << cycle[i] << " ";
}
}else cout << "NO" << endl;
}
```
---
## Floyd-Warshall 演算法
### 解說：
dis~k,i,j~ = min(dis~k,i,j~, dis~k−1,i,k~ + dis~k−1,k,j~)
* 每次多考慮一個可以經過的點 (k)
* 將 k 當作中繼點，更新 i 到 j 的距離
---
### 題目：
#### CSES - shortest route II
> https://cses.fi/problemset/task/1672
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define maxn 505
#define inf 1e18
#define int long long
using namespace std;
int n, m, q, dist[maxn][maxn];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> q;
//把dist[i][j] 預設到inf
for (int i=1; i<=n; ++i){
for (int j=1; j<=n; ++j){
if (i!=j) dist[i][j] = inf;
}
}
//輸入到dist (輸入有可能重複)
for (int i=1; i<=m; ++i){
int u, v, w; cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
}
//主要程式
for (int k=1; k<=n; ++k){
for (int i=1; i<=n; ++i){
for (int j=1; j<=n; ++j){
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
}
//i點到j點的最短距離為 dist[i][j]
for (int i=1; i<=q; ++i){
int a, b; cin >> a >> b;
if (dist[a][b] != inf) cout << dist[a][b] << endl;
else cout << -1 << endl;
}
}
```
#### Ex - Directed Graph and Query
> https://atcoder.jp/contests/abc287/tasks/abc287_h
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define maxn 2005
#define maxq 10005
#define inf 1e9
using namespace std;
int n, m, q, ans[maxq]; pair<int, int> p[maxq];
bitset<maxn> bt[maxn];
//bt[i][j] 存是否可以從i到j
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=1; i<=m; ++i){
int u, v; cin >> u >> v;
bt[u][v] = 1;
}
cin >> q;
for (int i=1; i<=q; ++i){
int a, b; cin >> a >> b;
p[i] = {a, b}; //處存要找的點
ans[i] = -1; //default
}
for (int k=1; k<=n; ++k){
for (int i=1; i<=n; ++i){
if (bt[i][k]) bt[i] |= bt[k];
//若i可以到達k，則k可以到達的i也可以到達 (取or)
}
for (int i=1; i<=q; ++i){
//試著去更新我們要找的點
if (ans[i] == -1 && bt[p[i].first][p[i].second]){
//若可以到達的話，則去試著更新答案
//因為要找ans[i]的min值 -> k的min值
//因為k是由小到大去找的，所以第一次遇到可以的k最會是k的min值
ans[i] = max({p[i].first, p[i].second, k});
}
}
}
for (int i=1; i<=q; ++i) cout << ans[i] << endl;
}
```
---
ok bye
Sign in with Wallet
Connect another wallet