# Edmonds-Karp 演算法與 Dinic 演算法
接續[最大流-最小割定理](https://hackmd.io/@ShanC/maxflow-mincut-theorem)，本篇筆記會講講為什麼需要更好的演算法去找最大流量。總共會聊到兩種演算法 : Edmonds-Karp 演算法與 Dinic 演算法
競程會用的應該只有 Dinic 演算法而已，所以如果只想把這裡當速食店的話讀 Dinic 演算法那段就好
## Ford-Fulkerson 演算法的問題
### 時間複雜度太大 (or 不確定)
在[最大流-最小割定理](https://hackmd.io/@ShanC/maxflow-mincut-theorem)中，有講到 Ford-Fulkerson 演算法，這是由 Ford 與 Fulkerson 在 1954 年提出。然而這演算法最大的問題就在於，其並沒有明確的說明要如何在圖中找出一條 $s$-$t$ 路徑，所以我們其實並不知道實作起來的複雜度為何。~~由於很多數學家不見得有時間複雜度的觀念~~，~~他們很多時候只會說明某某東西存在卻不說要怎麼找~~。演算法的時間複雜度在最差情況下恐怕會來到指數時間 (exponential running time)，當然這跟二進制的編碼長度也有關係。因定義不夠明確的緣故，Ford-Fulkerson 演算法有時候會被稱為「方法」而不是「演算法」
### 好的演算法?
那麼 Ford 與 Fulkerson 有提出演算法去解決算法的問題嗎? Fulkerson 算是有，只是用的是線性規劃 (Linear Programming) 的方法，詳情可以看[這篇 paper](https://onlinelibrary.wiley.com/doi/10.1002/nav.3800020407)。想知道線性規劃是什麼可以修修看作業研究 (Operation Research)，反正我是沒修過
話雖如此，在之後其他人的研究中仍有人提出好的演算法來解決這個問題，其中就包含許多大師們的傑作。Edmonds 與 Karp 在 1972 年提出的演算法、Dinitz 在 1970 年提出的演算法的變體是至今仍常被使用的演算法
## Edmonds-Karp 演算法
Edmonds-Karp 演算法就只是用 BFS 實作 Ford-Fulkerson 演算法而已，實際上沒有太複雜。由於演算法的部分在[這篇](https://hackmd.io/@ShanC/maxflow-mincut-theorem#Ford-Fulkerson-%E6%BC%94%E7%AE%97%E6%B3%95)講過了，所以直接給程式碼與 Ford-Fulkerson 演算法的 Pseudocode，兩者幾乎一模一樣，卻有著截然不同的複雜度
### 實作程式碼
#### Ford-Fulkerson 演算法的 Pseudocode
```c
FordFulkerson(N, s, t)
let Gf as the residual graph and cf be the residual capacity
for each e in N.E
f(e) = 0
while there exists a path P from s to t in Gf
cf(P) = min{cf(e) | e is in P}
for each e in P
let eR be the reversed edge
if e in N.E
then f(e) = f(e) + cf(P)
else f(eR) = f(eR) - cf(P)
return f
```
#### C++ 實作 Edmonds-Karp 演算法
```cpp
int n;
int cap[MXN][MXN];
vector<int> adj[MXN];
int bfs(int s, int t, vector<int>& parent) {
fill(parent.begin(), parent.end(), -1);
parent[s] = -2;
queue<pair<int, int>> q; // 儲存 {節點, cf(P)}
q.push({s, INF});
while (!q.empty()) {
int cur = q.front().first;
int flow = q.front().second;
q.pop();
for (int next : adj[cur]) {
// 判斷此點是否走過
if (parent[next] == -1 && cap[cur][next]) {
parent[next] = cur;
// new_flow 就是傳路徑上最小的 flow，也就是 cf(P)
int new_flow = min(flow, cap[cur][next]);
if (next == t) // 如果走到 t 就是找到 path 了
return new_flow;
q.push({next, new_flow});
}
}
}
return 0;
}
int Edmonds_Karp(int s, int t) {
int flow = 0;
vector<int> aug_path(n);
int new_flow;
while (new_flow = bfs(s, t, aug_path)) { // 找一條 augmenting path P
flow += new_flow;
int cur = t;
while (cur != s) { // 沿著 augmenting path P 走
int prev = aug_path[cur];
// e = (cur, prev), eR = (prev, cur)
cap[prev][cur] -= new_flow;
cap[cur][prev] += new_flow;
cur = prev;
}
}
return flow;
}
// 程式碼修改自 CP-algorithms
```
### 時間複雜度分析
首先，令 $E$ 代表邊數、$V$ 代表節點數
#### BFS 的時間複雜度
通常流量網路圖中的 $E$ 會比較大，因此 BFS 會是 $O(V+E)=O(E)$
#### 引理 : 最短距離隨著迭代次數單調遞增
證明使用反證法，也就是假設「最短距離隨著迭代次數單調遞減」。考慮 $f$ 是在迭代前的 flow，會符合假設，而 $f'$ 是迭代後的 flow。根據假設，會存在一個點 $v$ 使得迭代前後 $s, v$ 的最短距離呈現不等式 $dis_{f'}(s, v) < dis_{f}(s, v)$ ...(1)。令在迭代後 $s, v$ 最短路徑再找一個點 $u$ 使得 $dis_{f'}(s, u) = dis_{f'}(s, v) - 1$ ...(2)
<img src="https://hackmd.io/_uploads/B1Z3B6bXeg.png" style="margin: 0 auto; display: block; width: 400px">
$~$
因為在 $f$ 時會挑選 $s, v$ 路徑 (紅色) 走，而不是選擇藉由 $s, u$ 路徑走到 $v$，因此迭代後到 $u$ 的最短距離不會減少 $dis_{f'}(s, u) \geq dis_{f}(s, u)$ ...(3)
根據最短距離的函數會符合[三角不等式](https://hackmd.io/@ShanC/Dijkstra#%E9%AC%86%E5%BC%9B-Relax)，可以得到 : $dis_f(s, v) \leq dis_f(s, u) + 1$
$\Rightarrow dis_f(s, u) \geq dis_f(s, v) - 1$ ...(4)
由 (3)、(4) : $dis_{f'}(s, u) \geq dis_f(s, v) - 1$
$\Rightarrow dis_{f}(s, v) \leq dis_{f'}(s, u) + 1$ ...(5)
由 (2)、(5) : $dis_{f}(s, v) \leq dis_{f'}(s, v)$ ...(6)
我們以上的推論都是正確的，然而，這條不等式 (6) 違背原本的假設 (1)，因此假設是錯的，所以我們得到「最短距離隨著迭代次數單調遞增」
#### while 迭代次數
首先，定義一條邊是 critical 若且為若他的容量等於剩餘路徑的容量。每次找到一條 augmenting path 時，就會出現 critical 的邊。令 $u, v$ 之間有邊連接，則 $dis_{f}(s, v) = dis_{f}(s, u) + 1$
一旦在迭代中 $f$ 把 $(u, v)$ 填滿了容量，這條邊就會從 residual graph 消失。這條邊如果要再出現的話，僅有可能是 $(v, u)$ 出現在 augmenting path 上。令 $f'$ 就是屬於這種狀況，則會出現等式 $dis_{f'}(s, u) = dis_{f'}(s, v) + 1$
由引理 $dis_f(s, v) \leq dis_{f'}(s, v)$ 代入等式可得 : $dis_{f'}(s, u)\geq dis_{f}(s, v) + 1$
再結合上一個等式 $dis_{f}(s, v) = dis_{f}(s, u) + 1$ 可得 : $dis_{f'}(s, u)\geq dis_{f}(s, u) + 2$
這不等式說明 $(u, v)$ 從第一次成為 critical 到下一次成為 critical，$s$ 到 $u$ 的距離最少會增加 $2$
從 $s$ 到 $u$ 的路徑不包含 $s, u$，其中的節點數會是 $V-2$，因此推得一條邊成為 critical 的次數最多是 $\cfrac{V-2}{2}=O(V)$
一張圖總共有 $E$ 條邊，因此總迭代次數為 $E\times O(V)=O(VE)$
#### 總時間複雜度
- BFS 的時間複雜度 : $O(E)$
- 總共迭代次數 : $O(VE)$
總時間複雜度 : $O(VE)\times O(E)=O(VE^2)$
## Dinic 演算法
首先要說明的是，發明這個演算法的人叫做 Dinitz，只是當時 Even 在推廣演算法時，一直被錯誤的讀音念成 Dinic，漸漸地，這也成為這演算法的名稱
Dinic 演算法可以說是 Edmonds-Karp 演算法的延伸，但其實兩種演算法的發明者都沒有參考彼此的想法，都是各自獨立研究出來
### Dinic 的主要想法
假設樂奈喵想要吃抹茶パフェ，她只知道抹茶パフェ位於東方，那該如何走才能吃到呢?
樂奈喵只有可能走三種方位 : 東、東北、東南，而其他方位並不會被考慮
<img src="https://hackmd.io/_uploads/SJeZNyA-Xlx.png" style="margin: 0 auto; display: block; width: 600px">
$~$
Dinic 演算法的想法就有點像這樣，用類似 heuristic 的方法去避免不可能走的路徑。事實上，演算法所利用的就是 BFS 會產生的性質 - **分層**
### 分層圖 Level Graph
以下圖 $N$ 為例，$s$ 是源點、$t$ 是匯點，實邊是原本的邊、虛線邊是 residual 邊
<img src="https://hackmd.io/_uploads/HybJB0W7xx.png" style="margin: 0 auto; display: block; width: 650px">
$~$
假設從 $s$ 出發開始 BFS，那就可以得到分層圖
同時透過走訪整張圖，也可以確認從 $s$ 到 $t$ 是否存在一條路徑
<img src="https://hackmd.io/_uploads/HkQ_L0b7ge.png" style="margin: 0 auto; display: block; width: 650px">
這時我們可以由分層圖知道，若要走從 $s$ 到 $t$ 的路徑，那麼每走到下一個節點，level 都要嚴格遞增。因此我們把沒有遞減的邊拿掉 (實作上忽略就好)，並用 DFS 走訪，就可以找到 augmenting path
<img src="https://hackmd.io/_uploads/H10DdRb7ee.png" style="margin: 0 auto; display: block; width: 650px">
之後的步驟就是做邊的加值或減值，然後重複以上步驟
### 演算法步驟
1. 用 BFS 建立 level graph，並搜尋是否有路徑到 $t$。若沒有就離開迴圈，回傳 flow
2. 用合法的邊進行 DFS，並一邊計算每條邊的 flow 值
3. 重複 1~2
其實跟 Edmonds-Karp 的想法差不多，只是多了 level graph 作為限制
### 實作程式碼
```cpp
const int MXN = 2e3 + 5;
const int INF = INT_MAX;
// 每條邊都記錄三個訊息 : 到哪裡、流量、反邊存在哪
struct Edge {
int v, flow, re_id;
};
int n, s, t, m = 0, level[MXN];
vector<Edge> E[MXN]; // 把兩種圖都建在同一個上面
void add_edge(int u, int v, int f) {
E[u].push_back({v, f, (int)E[v].size()}); // 原本的 graph
E[v].push_back({u, 0, (int)E[u].size() - 1}); // residual graph
}
bool BFS() {
// level 就是 BFS 樹高
for (int i = 0; i < n; i++)
level[i] = -1;
queue<int> que;
que.push(s);
level[s] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
for (Edge &it : E[u]) {
// 每次就看可以流的邊
// 讓他們的距離 + 1
if (it.flow > 0 && level[it.v] == -1) {
level[it.v] = level[u] + 1;
que.push(it.v);
}
}
}
// 如果 t 能夠被走到，代表一定有 augmenting path
return level[t] != -1;
}
int DFS(int u, int nf) {
if (u == t)
return nf;
int res = 0;
for (auto &it : E[u]) {
// 這條邊必須是原本圖上的，並且要符合 level 性質
if (it.flow > 0 && level[it.v] == level[u] + 1) {
// 這些加值與減值要自己對照著看囉
int tf = DFS(it.v, min(nf, it.flow));
res += tf;
nf -= tf;
it.flow -= tf;
E[it.v][it.re_id].flow += tf;
if (nf == 0)
return res;
}
}
// 若 res 為 0 則代表沒有邊可以走到 u
if (!res)
level[u] = -1;
return res;
}
int dinic(int res = 0) {
// BFS 找 level 並判斷能不能走到 t
while (BFS())
// DFS 從 level 圖中找到一條 augmenting path 並計算 flow
res += DFS(s, INF);
return res;
}
// 修改自海大競程講義
// 此程式碼不含當前弧優化
```
### 當前弧優化
在 DFS 時，會發現有些死路被檢查過很多次，這會降低演算法的效率。因此可以利用減枝 (pruning) 的方法。簡單來說，就是再搞一個指標陣列去維護某些東西，非常簡單的一個做法。然而這份模板畢竟是 for 競賽用途，天機不可洩漏，在這就不放優化版的 code，詳細可以自己查
P.S. ShanC 很好心地在這邊這邊放優化的[那篇論文](https://epubs.siam.org/doi/10.1137/0204043)唯一有提到減枝的地方
<img src="https://hackmd.io/_uploads/B1TLYwfmlx.png" style="margin: 0 auto; display: block">
### 時間複雜度
這裡的證明有點像是在講廢話，所以只講結論
#### 階段數量
- 引理 1 :
從 $s$ 到每個頂點的距離在每次迭代後都不會減少，即 $level_{i+1}[v] \ge level_i[v]$
- 引理 2 :
從 $s$ 到匯點 $t$ 的距離是嚴格增加的，即 $level_{i+1}[t] > level_i[t]$
這個演算法會分成好幾個階段，從這兩個引理可以得出結論，階段數量少於 $V$。因為 $level[t]$ 每次階段都會增加，但它不可能大於 $V-1$
#### 每一階段 DFS 總時間
- 尋找阻塞流的方法是使用 DFS 從 $s$ 推送流到 $t$，直到無法再推送為止
- 為了提高效率，需要移除那些無法再用於推送的邊。可以通過在每個頂點維護一個指標陣列，指向下一條可以使用的邊來實現
- 單次 DFS 執行需要 $O(k+V)$ 時間，其中 $k$ 是指標推進的次數
- 所有 DFS 執行的指標推進總數不超過 $E$。另一方面，執行總次數不超過 $E$，因為每次執行都會少一條邊 (容量滿)
每一階段 DFS 總時間 : $O(VE)$
#### 總時間複雜度
$O(V \cdot VE) = O(V^2E)$
### 特例 : $0$/$1$ 流量網路
Even 跟 Tarjan 在 [1975 年的 paper](https://epubs.siam.org/doi/10.1137/0204043) 裡有證明在容量只有 $0$ 或是 $1$ 的流量網路圖裡面，時間複雜度會有所不同。由於證明太長，就不放上來了，簡短版可以看[這篇](https://cp-algorithms.com/graph/dinic.html)
#### 情形 1 : 容量為單位容量 ($0$ 或 $1$)
這種情形有兩種不同的評估方式，分別會跑出兩種不同的複雜度
- 最多只會有 $\sqrt E$ 次迭代 : $O(E\sqrt E)$
- 最多只會有 $V^{\frac{2}{3}}$ 個階段 : $O(EV^{\frac{2}{3}})$
這種評估可以用在 [Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem#Menger-%E5%AE%9A%E7%90%86)描述的圖當中
#### 情形 2 : 單位容量，且入邊或出邊唯一
用流量網路解[二分圖匹配](https://hackmd.io/@ShanC/bipartite-and-flow#%E6%9C%80%E5%A4%A7%E6%B5%81-%E6%9C%80%E5%B0%8F%E5%89%B2%E5%AE%9A%E7%90%86%E8%88%87-K%C5%91nig-Egerv%C3%A1ry-%E5%AE%9A%E7%90%86)就是屬於這種情況
- 時間複雜度 : $O(E\sqrt V)$
## 一些歷史
這段主要參考自 [Dinitz 親自闢謠](https://link.springer.com/chapter/10.1007/11685654_10)
如果去查論文發表時間的話，可能會發現一點。邏輯上，Dinic 演算法算是利用 Edmonds-Karp 演算法的機制，所以應該是 Edmonds-Karp 演算法要比較早發表。然而，事實正好相反，Dinic 演算法是 1969 年被發明，1970 年發表在 [Doklady Akademii Nauk SSSR](https://en.wikipedia.org/wiki/Proceedings_of_the_USSR_Academy_of_Sciences)，而 Edmonds-Karp 演算法則是在 1972 年發表。兩者是各自獨立發表，沒有任何關聯
在 1970 年代，美蘇冷戰的緣故，導致資訊傳遞不發達。西方世界不容易知道蘇聯內部的技術發展到什麼階段。西方的 Shimon Even 與他的學生 Alon Itai，想要讀懂 Dinitz 發表的演算法，然而礙於期刊限制只能寫四頁，要讀懂實在不容易，因此他們花了三天的時間研究，最後理解了 Dinitz 的作法。
Shimon Even 之後就一直在課堂上推廣這套算法，並且誤將 "Dinitz" 念成 "Dinic"。從此，西方世界都稱這個演算法為 Dinic's algorithm。然而，"Dinic's algorithm" 與原本的 "Dinitz's algorithm" 其實有些不同。現在我們競程常用的其實是 Even 跟 Itai 弄出來的版本，而不是原版，就...還挺搞笑的 XD
----
## 參考資料
- D.B.West - Introduction to Graph Theory 2/e
- Introduction to Algorithms, Fourth Edition
- [Ford and Fulkerson - Maximal flow through a network. Canadian Journal of Mathematics](https://archive.org/details/sim_canadian-journal-of-mathematics_1956_8_3/page/398/mode/2up)
- [Schrijver - Paths and Flows - a Historical Survey](https://ir.cwi.nl/pub/18229/18229B.pdf)
- [Edmonds and Karp - Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems](https://web.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf)
- [Even and Tarjan - Network Flow and Testing Graph Connectivity](https://epubs.siam.org/doi/10.1137/0204043)
- [台師大演算法筆記 - flow](https://web.ntnu.edu.tw/~algo/Flow.html)
- [維基百科 - Edmonds–Karp algorithm](https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm)
- [維基百科 - Dinic's algorithm](https://en.wikipedia.org/wiki/Dinic%27s_algorithm)
- [CP Algorithms - Maximum flow - Ford-Fulkerson and Edmonds-Karp](https://cp-algorithms.com/graph/edmonds_karp.html)
- [CP Algorithms - Maximum flow - Dinic's algorithm](https://cp-algorithms.com/graph/dinic.html)
- [Brilliant - Edmonds-Karp Algorithm](https://brilliant.org/wiki/edmonds-karp-algorithm/)
- [海大競程 - 匹配與網路流](https://hackmd.io/@LeeShoWhaodian/flow#/) (裡面似乎有點錯)
- [吃手手嚇到 - Edmonds-Karp 演算法](https://hackmd.io/@IiFm7xjrSOC3EYPOk9Mx4A/Hyekh6h39)
- [Dinic's Algorithm | Network Flow | Graph Theory](https://youtu.be/M6cm8UeeziI?si=qEYSdYffwn_bDswO)
- [Dinitz’ Algorithm: The Original Version and Even’s Version](https://link.springer.com/chapter/10.1007/11685654_10)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/6/9
Sign in with Wallet
Connect another wallet