--- # System prepended metadata title: '***Edmonds-Karp 演算法***' --- # ***Edmonds-Karp 演算法*** 在閱讀本篇前，讀者需要先大致知道 *get maximun flow* , *residual network* 及 *flow network* 的內容 本篇將介紹 *Edmonds-Karp* 如何運作 , 並證明他的 *time complexity* , 最後附上c++ code ## ***augmenting path*** s 為 source , t 為 tink f : *flow network* 中的 flow G~f~ : *redidual network* c~f~ : *residual network* 中的 capacity E~f~ : *residual network* 中存在的 edge，若 $c_f(u,v) > 0$ 則 $(u,v) \in E_f$ *augmention* : 要增加多少 flow from $s$ to $t$ 在 *residual network* 中，若可以找到一條 $s$ ~ $t$ 的路徑 $p$ 則稱此 $p$ 為一條 *augmenting path* 並且，*residual network* 可能同時擁有1條以上的 *augmenting path* 若 $p$ 存在，代表還有多的 flow 可以從 $s$ 流向 $t$ 定義 $c_f(p) = min\ \{ c_f(u,v) : (u,v)\ is \ on \ p \}$ 表 $p$ 最多能有 $c_f(p)$ 從 $s$ 流向 $t$ 也就是 *augmention* 的值 $p_1$ $(s-2-1-t)$ 為一條 *augmenting path* $c_f(p_1) = 4$ ![](https://i.imgur.com/19aSeyL.png =50%x) ###### 上圖為初始的 flow network 數值為 flow/capacity ## ***Ford-Fulkerson method*** 也有人會稱作 *Ford-Fulkerson* *algorithm* 算是 *Edmonds-Karp* 的前身 流程與 *Edmonds-Karp* 幾乎相同，只有選擇 *augmenting path* 上有差 *Ford-Fulkerson* 無限制如何選擇 *augmenting path* 以下以一個 *flow network* 作範例 用 *Ford-Fulkerson* 並求出他的 *maximun flow* (此圖參考CLRS) ![](https://i.imgur.com/uYtJgc8.png =50%x) 原始 *flow network* 左為 *capacity network* / 右為 *flow network* 紅線為選擇的 *augmenting path* # ![](https://i.imgur.com/O4361Ws.png =48%x) ![](https://i.imgur.com/z8cBqR5.png =50%x) 以 $c_f(p)$ 為增加 flow 做 *augmention*，則 $(s,1)$ $(1,3)$ $(3,2)$ $(2,4)$ $(4,t)$ 之 flow 皆+4 右圖 augmention 後的 *flow network* # ![](https://i.imgur.com/qxkksyU.png =48%x) ![](https://i.imgur.com/ry2GgSO.png =48%x) 因上個 *augmention* 中 flow 增加了4，因此 $c_f(s,1)\ c_f(1,3) \ c_f(3,2) \ c_f(2,4) \ c_f(4,t)$ 皆-4 而 $c_f(4,t) = 0$ 故 $(4,t)$ 消失於 $E_f$ 中 反之，$c_f(1,s)\ c_f(3,1) \ c_f(2,3) \ c_f(4,2) \ c_f(t,4)$ 皆+4，故新增於 $E_f$ 中 # ![](https://i.imgur.com/jGOdyi6.png =48%x) ![](https://i.imgur.com/jBRwDnL.png =48%x) 此 *augmention*，1往2的flow增加了4，故在右圖中，2往1的flow由4歸零 # ![](https://i.imgur.com/kEX6jPs.png =48%x) ![](https://i.imgur.com/Tgb4Jah.png =48%x) # ![](https://i.imgur.com/gH0lNoo.png =48%x) ![](https://i.imgur.com/qXuLP9U.png =48%x) # ![](https://i.imgur.com/QuR2KtT.png =50%x) 無 *augmenting path* 存在 # 由最後一張右圖可知 *maximun flow* = 23 ## **不佳的 *aumenting path*** 一個 *residual network* 可能存在一個以上的 *aumenting path* 如何選擇 *augmenting path* 會影響到演算法的執行效率 以下示範不好的 *augmenting path* : ###### 下圖皆為 residual network ## ![](https://i.imgur.com/QozHBM0.png =50%x) 選擇 $s-2-1-t$ 為 path，並增加 1 flow from s to t ## ![](https://i.imgur.com/IFt8P89.png =50%x) 選擇 $s-1-2-t$ 為 path，並增加 1 flow from s to t ## ![](https://i.imgur.com/mPNyy1A.png =50%x) 選擇 $s-2-1-t$ 為 path，並增加 1 flow from s to t ## 如此重複做下去，需要2000次才能結束 (得到 *maximun flow* ) 因此，*Ford-Fulkerson* 的時間複雜度與邊的 capacity 有關 也就是可能選到沒效率的 *augmenting path* *Edmonds-Karp* 利用 *bfs* 解決了這個問題，並把時間複雜度限制在 $O(VE^2)$ ## **BFS** 在 *Edmonds-Karp* 中， 利用 *bfs* 尋找 *residual network* 中 s to t 的 *shortest path* (此路徑長度取決於經過多少個邊) 因為將此 *shortest path* 作為 *augmenting path*，較有效率 為了證明這樣能將時間複雜度限制在 $O(VE^2)$，需先證明一個定理 : #### **Lemma1** : 在 *residual network* 中，對於所有 $v \in V - \{s,t\}$ $s$ 到 $v$ 的最短距離 $\delta_f(s,v)$ 會隨著 *augmention* 單調遞增 ## #### *proof* : 現在有一個 *augmention* : AG 進行 $f$ 為在 AG 之前的 flow $f'$為在 AG 之後的 flow 所要證明為 $\delta_{f'}(s,v) \ge \delta_f(s,v)$ 這裡將使用反證法 假設 $v$ 為其中一個在 AG 後 $\delta(s,v)$ 減少的點 $\delta_{f'}(s,v) < \delta_f(s,v)$ 令 $p=s \rightarrow ... \rightarrow u \rightarrow v$ 為 $v$ 跟 $u$ 之 *shortest path* in $G_{f'}$ , 可得到 : $(u,v) \in E_{f'}$ $\delta_{f'}(s,u) = \delta_{f'}(s,v) - 1$ 不失一般性 : $\delta_{f'}(s,u) \ge \delta_f(s,u)$ 接下來，分別討論兩種狀況，分別是 $(u,v) \in E_f\ 和\ (u,v) \not\in E_f$ ## $(u,v) \in E_f \ :$ $\delta_f(s,v) \le \delta_f(s,u)+1$ $\ \ \ \ \ \ \ \ \ \ \ \ \le \delta_{f'}(s,u)+1$ $\ \ \ \ \ \ \ \ \ \ \ \ = \delta_{f'}(s,v)$ $\Rightarrow\delta_f(s,v) \le \delta_{f'}(s,v)$ 與所假設矛盾 ## $(u,v) \not\in E_f \ :$ 若 $(u,v) \not\in E_f \ 但\ (u,v) \in E_{f'}$ 則 $G_{f}$ 中的 *augmenting path* 必定包括 $(v,u)$ 這樣 $c_{f'}(u,v)$ 才會 > 0 $\therefore(v,u) \in E_f$ 且 $\delta_{f}(s,v) = \delta_{f}(s,u) - 1$ (因為*augmenting path* 為 *shortest path)* $\delta_{f}(s,v) = \delta_{f}(s,u) - 1$ $\ \ \ \ \ \ \ \ \ \ \ \ \le \delta_{f'}(s,u)-1$ $\ \ \ \ \ \ \ \ \ \ \ \ = \delta_{f'}(s,v)-2$ $\Rightarrow\delta_f(s,v) \le \delta_{f'}(s,v)-2$ 與所假設矛盾 ## 根據以上兩種種況皆矛盾，可知道此種 $v$ 點不存在 而之所以能有這個性質是因為所選 augmenting path 為 shortest path 有了此 lemma 就能夠證明 *Edmonds-Karp* 的時間複雜度 ## **時間複雜度證明** #### **Theorem1** : 在 *Edmonds-Karp* 中，augmentions 的數量為 $O(VE)$ 也就是找了幾次 *augmenting path* ## #### *proof* : $(u,v) \in E_f$ 我們稱 $(u,v)$ is critical 若 $c_p(u,v)=c_p(p)$ , $p$ 為 *augmenting path* 換句話說，就是 $(u,v)$ 在 $p$ 擁有最小的 capacity 令 $(u,v)$ is critical $\therefore\delta_{f}(s,u) = \delta_{f}(s,v) - 1$ 因為 $(u,v)$ critical , 在 *augmention* 後 , $c_f(u,v)=0$, $(u,v)$會消失在 *residual network* 若 $(u,v)$ 要再次出現在 $G_f$ 中，需要有一次的 *augmention* 且 $(v,u)$ 在 *augmention path* 上 假設這時的 flow 為 $f'$ $\therefore\delta_{f'}(s,v) = \delta_{f'}(s,u) - 1$ $\delta_{f'}(s,u) = \delta_{f'}(s,v) + 1$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ge \delta_f(s,v)+1 \ \ :\ \ lemma1$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ = \delta_{f}(s,u)+2$ $\Rightarrow\delta_{f'}(s,v) \ge \delta_{f}(s,v)+2$ - $v \in V-\{s,t\}$ 的 $\delta_f(u,v)$ 最大值為 $|V|-2$ - 間隔兩次 critical edge，$\delta_f(u,v)$ 至少增加 2 $\Rightarrow$ 一條 $(u,v)$ 成為 *critical edge* 的次數最多為 $(|V|-2)/2$ , 即$O(V)$ 所以在一次 *Edmonds-Karp* 中共有 $O(VE)$ 條 *critical edge* 又每次 *augmention* 中，為 *critical edge* 的數量為常數 因此 *augmention* 的次數為 $O(VE)$ # 由以上 Thereom，*augmention* 的數量為 $O(VE)$ 又每次 *augmention* 時的 bfs 時間複雜度為 $O(V)$ 故 *Edmonds-Karp* 的時間複雜度為 $O(VE)*O(E)=O(VE^2)$ ## **code** ```CPP= #include #include #include #include using namespace std; //this time complexity is O(VE^2) struct node { int val; node *next; node (int x, node *t) { val = x; next = t; } }; class Solution { public: vector> cf; //點到點之間能走的capcity vector adj_list; vector preV; //augment path時的路徑的點的前一個點 vector> *edges; int n; Solution(int nt, vector> *edgs) { n = nt; edges = edgs; } void initial(int s, int t) { cf = vector>(n, vector(n,0)); adj_list = vector(n, nullptr); preV = vector(n, -1); for(vector &edge : (*edges)) { cf[edge[0]][edge[1]] = edge[2]; add_in_adj(edge[0], edge[1]); } } int get_max_flow(int s, int t) { initial(s,t); int new_flow, max_flow = 0; while((new_flow = bfs(n,s,t)) != -1) { //s~t 還存在 path augmention(new_flow, s, t); max_flow += new_flow; } return max_flow; } int bfs(int n, int s, int t) { //回傳 cf(p) , p 為 augmenting path queue que; que.emplace(s); vector visit(n, false); visit[s] = true; while(!que.empty()) { int u = que.front(); que.pop(); for(node *cur = adj_list[u]; cur; cur = cur->next) { int v = cur->val; if(!visit[v]) { visit[v] = true; preV[v] = u; //在 augemnting path裡，v的前一個點是u que.emplace(v); if(v == t) //已經找到 augment path return find_min_in_augpath(s,t); } } } return -1; } int find_min_in_augpath(int s, int t) { int cur = t, ret = INT32_MAX; while(cur != s) { ret = min(ret, cf[preV[cur]][cur]); cur = preV[cur]; } return ret; } void augmention(int val, int s, int t) { // val is the minimun value in augment path int cur = t; while(cur != s) { cf[preV[cur]][cur] -= val; cf[cur][preV[cur]] += val; if(cf[preV[cur]][cur] == 0) del_in_adj(preV[cur], cur); if(cf[cur][preV[cur]] == val) add_in_adj(cur, preV[cur]); cur = preV[cur]; } } void del_in_adj(int u, int v) { node *cur = adj_list[u]; if(cur->val == v) adj_list[u] = cur->next; else { while(cur->next->val != v) cur = cur->next; cur->next = cur->next->next; } } void add_in_adj(int u, int v) { node *tmp = new node(v, adj_list[u]); adj_list[u] = tmp; } }; int main(void) { int n, m; cin >> n >> m; //vertexs and edges num int u,v,cap,s,t; vector> edgs(m); for(int i=0; i> u >> v >> cap; edgs[i] = vector{u,v,cap}; } s=0, t=n-1; double start = clock(); Solution S = Solution(n,&edgs); cout << "the maximun flow is : " << S.get_max_flow(s,t) << '\n'; double end = clock(); cout << "花費時間(秒) : " << (end - start) / CLOCKS_PER_SEC ; return 0; } ``` 這是本人第一次寫hackmd，也是第一次在網路上發表自己的code 若有任何想法問題或需要改進的地方可以告訴我