[Algorithm] 최대 유량 문제

Maximum Flow Problem란?

Source s에서 Target t까지 최대한 보낼수 있는 유량을 구하는 문제

Ford-Fulkerson method

Residual Network에서 augmenting path가 더이상 존재하지 않을때까지 path에 augment값만큼 flow를 늘려나간다.

 

수도코드 1

Initialize flow f = 0;
while( there exists an augmenting path p in Gf )
{
    augment the flow along p;
}
Output the final flow f;

 

수도코드 2

Ford-Fulkerson(G, s, t)
{
    for (each edge (u, v) in E)
        f(u,v) = 0; f(v,u) = 0;

    // Gf : Residual Network
    while ( there exist a path p from s to t in Gf)
    {
        // cf(p) : augment path에서 가장 작은 값
        cf(p):= min {cf(u,v):(u,v) in p}

        // augment path에 cf(p)만큼 augment한다.
        for (each edge (u, v) in p) {
            f(u,v) = f(u,v) + cf(p);	// flow 값 update
            cf(u,v) = c(u,v) - f(u,v);	// Residual capacity도 update
            f(v,u) = -f(u,v);           // 역방향 flow update
            cf(v,u) = c(v,u) - f(v,u);  // 역방향 Residual capacity update
        }
    }
}

최악의 경우 1씩 augment해서 Edge의 개수 * maximum Flow 값인 $O(|E||f|)$ 시간복잡도가 걸릴수 있다.
F값이 exponential(지수) 일 수 있기때문에 polynomial(다항) 시간안에 풀지 못할수도 있다.

Edmond karp method

Ford-Fulkerson method에서 하나만 변경하면 되는데 Residual network에서 augmenting path를 찾을때 Breadth-First search로 찾는다.
그러면 가장 짧은 augmenting path를 우선으로 찾을 수 있다. 이 방법을 사용하면 augmenting 횟수는 $O(|E||V|)$로 보장 가능하다.
고로 총 시간은 $O(|E||f|) = O(|E|^2 |V|)$다.