# ***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$

###### 上圖為初始的 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)

 原始 *flow network*

左為 *capacity network* / 右為 *flow network*
紅線為選擇的 *augmenting path*

#

 

以 $c_f(p)$ 為增加 flow 做 *augmention*，則 $(s,1)$ $(1,3)$ $(3,2)$ $(2,4)$ $(4,t)$ 之 flow 皆+4
右圖 augmention 後的 *flow network*

#

 

因上個 *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$ 中

#

 

此 *augmention*，1往2的flow增加了4，故在右圖中，2往1的flow由4歸零

#

 

#
 
#

 無 *augmenting path* 存在
#

由最後一張右圖可知 *maximun flow* = 23

## **不佳的 *aumenting path***

一個 *residual network* 可能存在一個以上的 *aumenting path*
如何選擇 *augmenting path* 會影響到演算法的執行效率
以下示範不好的 *augmenting path* :
###### 下圖皆為 residual network
##

選擇 $s-2-1-t$ 為 path，並增加 1 flow from s to t

##

選擇 $s-1-2-t$ 為 path，並增加 1 flow from s to t

##

選擇 $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**

#include <iostream>
#include <vector>
#include <queue>
#include <time.h>
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<vector<int>> cf;  //點到點之間能走的capcity
    vector<node*> adj_list;
    vector<int> preV;  //augment path時的路徑的點的前一個點

    vector<vector<int>> *edges;
    int n;
    
    Solution(int nt, vector<vector<int>> *edgs) {
        n = nt;
        edges = edgs;
    }

    void initial(int s, int t) {
        cf = vector<vector<int>>(n, vector<int>(n,0));
        adj_list = vector<node*>(n, nullptr);
        preV = vector<int>(n, -1);

        for(vector<int> &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<int> que;
        que.emplace(s);
        vector<bool> 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<vector<int>> edgs(m);
    
    for(int i=0; i<m; i++) {
        cin >> u >> v >> cap;
        edgs[i] = vector<int>{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
若有任何想法問題或需要改進的地方可以告訴我