# 111 選手班 - 圖論
###### tags: `宜中資訊` `CP`
2022.08.12

## 大綱
- 最小生成樹
- prim
- kruskal
- 最短路
- Bellman-Ford
- Dijkstra
- Floyd-Warshall
- [110 Slide](https://hackmd.io/@Ccucumber12/BJGKlTRkt#/)

## 最小生成樹
### 問題
給定一張圖 $G(V,E)$
請找出 $V-1$ 條邊使得
- 形成一棵樹
- 邊權總和最小

### Kruskal
#### 想法
- 每次選擇邊權最小的邊
- 如果沒必要拿就忽略

#### 過程
- 將圖 $G$ 上的 $E$ 條邊排序
- 對於每條邊 $(u, v, w)$
- 如果 $u$, $v$ 不在同一個聯通塊
- 把 $w$ 加進答案
- 連接 $u$, $v$

#### 並查集
- 檢查 $u$, $v$ 是否在同一個聯通塊 $\Rightarrow$ 檢查是否在同一個集合
- 連接 $u$, $v$ $\Rightarrow$ 合併兩個集合

#### 證明
- 對於某一個時刻，假設已經選了一個集合 $F$
- 假設現在最小的邊 $e(u, v, w)$
- 如果 $u$, $v$ 不在同一個聯通塊且我們不選他
- $u$, $v$ 會被其他邊($e'$) 連接且 $e'_w > e_w$
- 在最後把 $e$ 加進來會形成一個環且此時可以把 $e'$ 拔掉形成更小的 MST

#### 時間複雜度
- 排序: $O(ElogE)$
- DSU: $O(E\alpha(V))$
- Total: $O(ElogE)$

### Prim
- 設任一點當根
- 找到最小的相鄰邊加進解集合
- 重複直到所有邊都被加入

#### Heap
- 找到集合中最小的邊
- 把邊加入集合

#### 時間複雜度
- 找集合內最小邊: $O(ElogE)$
- 把邊加入集合: $O(ElogE)$
- 總和: $O(ElogE)$
- Fibonacci Heap優化: $O(VlogV + E)$

## 最短路
### 題目
- 給定一張帶權圖（有向 or 無向）
- 請找到一個 $S$ 走到 $T$ 的路徑
- 使得路徑權重總和最小
- 型態:
- 單源最短路 Single-Source Shortest Path
- 全點對最短路 All-Pairs Shortest Path

### 戴克斯特拉演算法
- Dijkstra
- 單點源最短路
- 不能有負邊
- 最佳時間複雜度

#### 鬆弛
- 設 $S$ 是目前的最短路集合
- 把所有 $S$ 連出去的邊鬆弛
- 把相鄰最小的點 $v$ 加進 $$
- 重複直到所有點都在 $S$ 內

#### Heap
- 找到集合內最小的點
- 把新鬆弛的點加進集合內
- $\implies$ priority_queue

#### 證明
- DP
- 如果不選擇最小的點
- 之後再過去只會更慢

#### 時間複雜度
- 找到最小: $O(E\log E)$
- 插入最小的點: $O(E\log E)$
- Total: $O(E\log E)$

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> g[100010] ; // <b, w>
const int INF = 0x3f3f3f3f ;

int main() {
    int n, m, s ;
    cin >> n >> m >> s ;
    for(int i=0; i<m; ++i) {
        int a, b, w ;
        cin >> a >> b >> w ;
        g[a].push_back(make_pair(b, w)) ;
        g[b].push_back(make_pair(a, w)) ;
    }

    priority_queue<pair<int,int>> pq; // <-dist[i], i>
    vector<int> dist(n + 1, INF) ;
    dist[s] = 0 ;
    for(auto i:g[s]) { // <b, w>
        pq.push(make_pair(-(dist[s] + i.second), i.first)) ;
    }

    while(pq.size() != 0) {
        auto u = pq.top() ; // <-dist[i], i>
        pq.pop() ;

        if(dist[u.second] != INF) continue ;
        dist[u.second] = -u.first ;
        for(auto i:g[u.second]) { // <b, w>
            if(dist[i.first] == INF)
                pq.push(make_pair(-(dist[u.second] + i.second), i.first)) ;
        }
    }

    for(int i=1; i<=n; ++i) cout << dist[i] << ' ' ;
    cout << endl ;
}

:::

### 貝爾曼-福特演算法
- Bellman-Ford
- 單點源最短路
- 支援負邊
- 尋找負環

#### 鬆弛
- 設 $\text{dist}(u)$ 為起點 $S$ 到點 $u$ 的最短路
- $\text{relax}(u,v)$: $\text{dist}(u) = \min(\text{dist}(u), \text{dist}(v) + \text{len}(v,u)$
- 對於每條邊 $(u,v) \rightarrow \text{relax}(u,v)$
- 重複直到無法在鬆弛任何 $dist(u)$

#### 時間複雜度
- 最多鬆弛 $V-1$ 次
- 每次最少會把一個點鬆弛成正解
- 總共只有 $V-1$ 個點要鬆弛
- $O(VE)$

#### 負環
- 第 $V$ 次還是成功鬆弛了某個點
- $\implies$ 存在負環

[負環模板題](https://www.luogu.com.cn/problem/P3385)

#### SPFA
- 只有相鄰的邊才要有可能需要鬆弛
- $\implies$ queue
- $O(E) \sim O(VE)$

### 弗洛伊德演算法
- Floyd-Warshall
- 全點對最短路
- 實作簡單
- 找最小環

#### 鬆弛
- Relax
- $\delta(s,t) = s$ 到 $t$ 的距離
- $\delta(s,t) = \min(\delta(s,t),\ \delta(s,i)+\delta(i,t))$
- 利用點 $i$ 進行鬆弛

#### DP
- 設 $D_{i,j,k}$ 代表點 $i$ 到點 $j$ 利用前 $k$ 個點進行鬆弛後的最短路。
- 如果經過 $k$: $D_{i,j,k} = D_{i,k,k-1} + D_{k,j,k-1}$
- 如果沒經過 $k$: $D_{i,j,k} = D_{i,j,k-1}$
- $\implies$ $D_{i,j,k} = \min(D_{i,j,k-1}, D_{i,k,k-1} + D_{k,j,k-1})$

#### 簡化
- $dp[i][j][k] = \min(dp[i][j][k-1], dp[i][k][k-1], dp[k][j][k-1])$
- $dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k][j])$

#### 時間複雜度
- $O(V^3)$
- 常數小

#### KIJ

for(int k=1; k<=n; ++k)
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) ;

### 比較
| | Floyd-Warshall | Bellman-Ford | Dijkstra |
| -------- | -------------- | ------------------- | ------------- |
| Time | $O(V^3)$ | $O(VE)$ | $O(E\log E)$ |
| Problem | All Pairs | Single Source | Single Source |
| Negative | O | O | X |
| Usage | Smallest cycle | Negative cycle | Fast |

## 題單
- [Contest](https://vjudge.net/contest/510093#overview)
- Password: `111apcs`