# 圖論 負權最短距離
[](https://hackmd.io/2AgFp0PORdahaCEV6ETkbQ)
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
----
## 為何不能用dijkstra
使用dijkstra權重需要都 $\ge0$
權重$\lt 0$會怎樣?
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
會出現負循環
那要如何解決?
<!-- 就要用到的就要用到新的演算法
bellman ford algorithm -->
---
## 介紹 bellman ford
----
### 特點
1. 求點對點最短距離。
2. 允許權重<0
3. 可以檢測負環
----
### 算法核心
能不能藉由選擇走更短路，讓最後到終點的路是最短的。
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
1 -> 2 [label="-3"]
1 -> 2 [label="-2"]
}
```
----
有n個節點，起點最多經過n-1條路徑到終點。
```graphviz
digraph LR {
rankdir=LR;
a -> b [label="1"]
b -> c [label="2"]
c -> d [label="3"]
}
```
----
一次迴圈至少會選擇一條路徑
如果沒有負環，經過n-1次迴圈一定會找到最短路徑
在第n次還可以選擇更短的路徑，就一定有負環
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
| 1 | 2 | 3 | 4 |
|:---:|:--------:| -------- |:--------:|
| 0 | $\infty$ | $\infty$ | $\infty$ |
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1",color=Blue]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
| 1 | 2 | 3 | 4 |
|:---:|:---:|:--------:|:--------:|
| 0 | $1$ | $\infty$ | $\infty$ |
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1",color=Blue]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
| 1 | 2 | 3 | 4 |
|:---:|:---:|:--------:|:---:|
| 0 | $1$ | $\infty$ | $2$ |
----
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1",color=Blue]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
| 1 | 2 | 3 | 4 |
|:---:|:---:|:--------:|:---:|
| 0 | $1$ | $\infty$ | $2$ |
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3",color=Blue]
4 -> 3 [label="-2"]
}
```
| 1 | 2 | 3 | 4 |
|:----:|:---:|:--------:|:---:|
| $-1$ | $1$ | $\infty$ | $2$ |
----
----
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2",color=Blue]
}
```
| 1 | 2 | 3 | 4 |
|:----:|:---:|:---:|:---:|
| $-1$ | $1$ | $0$ | $2$ |
----
## 共N-1次迴圈後
```graphviz
digraph LR {
rankdir=LR;
1 -> 2 [label="1"]
2 -> 4 [label="1"]
3 -> 1 [label="1"]
4 -> 1 [label="-3"]
4 -> 3 [label="-2"]
}
```
| 1 | 2 | 3 | 4 |
|:----:|:---:|:---:|:---:|
| $-3$ | $-1$ | $-2$ | $0$ |
----
----
## 共N次迴圈後
| 1 | 2 | 3 | 4 |
|:----:|:---:|:---:|:---:|
| $-4$ | $-2$ | $-3$ | $-1$ |
----
### 複雜度
N是節點數
V是路徑的數量
----
### 複雜度
N是節點數
V是路徑的數量
O(NV)
---
## 模板題
[Cycle Finding](https://cses.fi/problemset/task/1197)
----
<!-- 我先為大家示範bellmen ford做這題的前半解答 -->
1. 使用相鄰串列tuple 或是vector存每個路徑
2. 做n個節點的表
3. 從哪裡更新的表
4. 做n次尋訪，用flag 看看這次尋訪有沒有更短的路，如果最後一次沒有則NO，有則YES。
----
那我請大家想想如何找其中一個負環?
----
### tuple type
```cpp=
vector<long long> dist(n,(1ll<<60));
vector<long long> path_From(n,-1);
dist[0] = 0;
vector<tuple<int, int, long long>> vec;
int a, b;
long long c;
for (int i = 0;i < m; ++i)
{
cin >> a >> b >> c;
vec.push_back(make_tuple(a-1,b-1,c));
}
bool flag = 0;
int u, v;
long long d;
for (int i = 0; i < n; ++i)
{
flag = 0;
for(auto it = vec.begin();it != vec.end();++it)
{
tie(u, v, d) = *it;
if(dist[u]+d<dist[v])
{
flag = 1;
dist[v] = dist[u]+d;
path_From[v] = u;
}
}
if(!flag)
{
break;
}
}
cout<<flag? "YES" : "NO";
return 0;
}
```
---
## 應用題
[High Score](https://cses.fi/problemset/task/1673)
反過來，我們要取得最大利益，就可能會有正環，要如何解決呢?
如何判斷起點到終點有沒有進入正環?
----
## 解
我們只對能到終點與起點的點做運算
可以先用dfs或bfs掃
看看起點有經過哪些點
反過來誰可以到達終點
----
```cpp=
void DFS(int op,vector<bool> &path,vector<vector<int>> &adj_List){
path[op] = 1;
for(auto it:adj_List[op])
{
if(!path[it])
{
DFS(it, path, adj_List);
}
}
}
```
----
```cpp=
int main(){
cin.tie(0)->sync_with_stdio(0);
cout.tie(0);
int n, m;
cin >> n >> m;
// adj list
long long tt = (~(1ll << 42) + 1);
vector<long long> dist(n,tt);
vector<tuple<int, int, long long>> tunnel(m);
vector<vector<int>> adj_List(n);//adj list
vector<vector<int>> bdj_list(n);//adj list
vector<bool> path(m,0);
vector<bool> repath(m,0);
bool flag = false;
for(int i=0,a,b,c; i<m; ++i)
{
cin >> a >> b>>c;
// --a;
// --b;
adj_List[a-1].push_back(b-1);
bdj_list[b-1].push_back(a-1);
tunnel.push_back(make_tuple(a-1,b-1,c));
}
DFS(0,path,adj_List);
DFS(n - 1, repath,bdj_list);
dist[0] = 0;
for (int i = 0; i < n;++i)
{ flag = 0;
for(auto it=tunnel.begin(); it!=tunnel.end();++it)
{
auto [v, u, d] = *it;
if(path[v]&&repath[u]&&dist[v]+d>dist[u])
{
flag = 1;
dist[u] = dist[v] + d;
}
}
}
// cout << bellman_Ford()<<"\n";
if (flag)
{
cout << "-1\n";
}
else
{
cout << dist[n - 1]<<"\n";
}
return 0;
}
```
---
## 參考資料
[cses graph session editorial(incomplete)](https://codeforces.com/blog/entry/79518) cses題目整理
[graph_editor](https://csacademy.com/app/graph_editor/) 好畫圖工具
[Draw-Graph](http://domen111.github.io/Draw-Graph/)
[印度大哥解High Score](https://cses.fi/paste/d9797aedd488129f116e2a/)
{"metaMigratedAt":"2023-06-17T14:20:40.375Z","metaMigratedFrom":"YAML","title":"圖論 負權最短距離","breaks":false,"contributors":"[{\"id\":\"e8522424-6893-41f1-959f-d5ae66fa6840\",\"add\":113998,\"del\":107589}]","description":"hackmd-github-sync-badge"}