140. Edmonds-Karp Algorithm

다음과 같은 그래프에서 포드-풀커슨 알고리즘으로 최대 유량을 구하는 경우를 생각해 보자.

포드-풀커슨 알고리즘은 증가 경로를 정하는 방법을 정의하지 않으므로, 운이 좋으면 증가 경로 $\text{S}$ - $\text{A}$ - $\text{T}$로 $10000$의 유량을 보내고 증가 경로 $\text{S}$ - $\text{B}$ - $\text{T}$로 $10000$의 유량을 보내서 두 번의 탐색으로 $20000$의 유량을 보낼 수 있다.

 

하지만 이 그래프에는 $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{T}$라는 증가 경로가 존재한다. 만약 이 경로를 선택할 경우 보낼 수 있는 유량은 $1$이고, 그러면 간선들의 유량은 다음과 같이 변한다.

이제 $\text{S}$ - $\text{B}$ - $\text{A}$ - $\text{T}$는 증가 경로가 된다. 이 경로를 선택할 경우 보낼 수 있는 유량은 $1$이고, 간선들의 유량은 다음과 같이 변한다.

만약 이런 방식으로 증가 경로를 선택하는 것을 반복한다면 최대 유량을 구하기 위해 증가 경로를 $20000$번 찾아야 한다. 즉, 포드-풀커슨 알고리즘의 시간복잡도는 $O((n+m)w)$이며, $w$가 크다면 경우에 따라 너무 느려지게 된다. ($w$는 그래프의 최대 유량)

---

에드몬드-카프 알고리즘(Edmonds-Karp Algorithm)은 포드-풀커슨 알고리즘에서 증가 경로를 찾는 방식을 BFS로 고정한 것이다. 이렇게 하면 $O(nm^2)$이라는 시간복잡도에 최대 유량을 구할 수 있게 된다. 시간복잡도를 구하는 과정은 다음과 같다.

• 최대 유량을 구하려는 그래프가 $G$이고, $G$에서 (역방향 간선을 포함해서) 유량을 더 보낼 수 있는 간선들만 남긴 그래프를 $G_A$라고 하고, 그 상태에서 증가 경로를 하나 찾아서 유량을 보낸 다음 유량을 더 보낼 수 있는 간선들만 남긴 그래프를 $G_B$라고 하자. 또한 $d_G(v)$를 그래프 $G$ 상에서 정점 $v$에서 싱크까지의 거리로 정의한다. 이제 임의의 정점에 대해 $d_{G_A}(v) \le d_{G_B}(v)$임을 보일 것이다.
• 먼저, 싱크 $\text{T}$에 대해 $d_{G_A}(\text{T}) = d_{G_B}(\text{T}) = 0$이다. 또한 $d_{G_B}(v) = \infty$인 경우 $d_{G_A}(v) \le \infty$이므로 $d_{G_A}(v) \le d_{G_B}(v)$이다.
• 만약 $v$가 싱크가 아니고 $d_{G_B}(v) \ne \infty$인 경우 $G_B$에서 $v$에서 싱크까지의 최단 경로가 존재하며, 경로상에 존재하는 정점들 중 $v$를 제외한 정점들에 대해서는 앞의 가정이 성립한다고 하자. 만약 $v$에 대해서도 이 가정이 성립함을 보일 수 있으면 귀납적으로 모든 정점에 대해 이 가정이 성립함을 보일 수 있게 된다.
• $G_B$에서 $v$에서 싱크까지의 최단 경로에서 $v$의 바로 다음에 오는 정점을 $u$라고 하면, $d_{G_B}(v) = d_{G_B}(u) + 1$이다. 또한 위에서 언급한 귀납법에 의해 $d_{G_B}(u) + 1\ge d_{G_A}(u) + 1$이다.
• 만약 $G_A$에 $v$에서 $u$로 가는 간선이 있었을 경우 $d_{G_A}(v) = d_{G_A}(u) + 1$이고, 그런 간선이 없었을 경우 $G_B$에 그 간선이 새로 생겼으므로 찾은 증가 경로에 $u$에서 $v$로 가는 간선이 포함되어 있다고 추론할 수 있다. 그렇다면 $G_A$는 $u$에서 $v$로 가는 간선을 포함해야 하며, 이 경우 $d_{G_A}(u) = d_{G_A}(v) + 1$이다.
• 두 경우 모두 부등식을 정리하면 $d_{G_B}(v) \ge d_{G_A}(v)$라는 결론을 얻는다.
• 다음으로 그래프의 증가 경로에서 더 보낼 수 있는 유량이 가장 적은 간선을 차단 간선이라고 하자. (이 용어는 공식적인 표현이 아니다.)
• 그래프에서 정점 $u$에서 $v$로 가는 간선이 여러 번 차단 간선이 되었을 경우, 처음에 정점 $u$에서 $v$로 가는 간선이 차단 간선이었다가, 증가 경로를 찾은 다음 $v$에서 $u$로 가는 간선이 차단 간선이 되었다가, 증가 경로를 더 찾은 다음 다시 $u$에서 $v$로 가는 간선이 차단 간선이 된 것이다. 앞의 가정에 의하면 이 과정에서 $d_G(v)$는 $2$ 이상 증가한다.
• $0 \le d_G(v) < n$이므로 $d_G(v)$가 $2$ 이상 증가하는 상황은 최대 $\lfloor n/2 \rfloor$번 발생한다. 따라서 각 간선이 차단 간선이 되는 횟수는 최대 $\lfloor n/2 \rfloor + 1$이다.
• 그래프에는 역방향 간선을 포함하여 총 $2m$개의 간선이 있으므로, 그래프의 최대 유량을 구하는 과정에서 생기는 차단 간선의 수는 최대 $2m \times (\lfloor n/2 \rfloor + 1)$이다.
• 한 번 증가 경로를 찾을 때 최소한 한 개의 차단 간선이 생기므로, 증가 경로를 찾는 횟수는 최대 $2m \times (\lfloor n/2 \rfloor + 1)$이다. 이를 간단하게 나타내면 $O(nm)$이다.
• BFS의 시간복잡도가 $\Theta(n + m)$이므로 BFS를 $O(nm)$번 실행하면 시간복잡도는 $O(nm(n + m)) = O(n^2m + nm^2)$이다.
• 증가 경로를 찾을 경우 소스, 싱크와 연결된 컴포넌트에서만 BFS를 실행하면 되며, 한 컴포넌트에서 간선의 수는 정점의 수 $- 1$ 이상이므로 BFS의 시간복잡도를 $\Theta(m)$으로 단순화할 수 있다. 이를 바탕으로 다시 계산한 최종 시간복잡도는 $O(nm^2)$이 된다.

 

따라서 기본적인 형태의 플로우 문제는 포드-풀커슨 알고리즘과 에드몬드-카프 알고리즘 중 더 빠른 알고리즘을 사용해서 문제를 해결하면 된다. 다만 포드-풀커슨 알고리즘이 유의미하게 더 빠른 문제가 거의 없기 때문에 일반적으로 에드몬드-카프 알고리즘이 많이 사용된다.

 

이제 구현을 살펴보자. 먼저 각 간선이 역방향 간선을 빠르게 참조해야 하므로, 간선을 저장할 때 역방향 간선의 인덱스를 함께 저장한다. 아래와 같은 방법으로 할 수 있다.

#import<bits/stdc++.h>
using namespace std;
vector<pair<int, int>>e[1005];
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back({y, e[y].size()});
        e[y].push_back({x, e[x].size() - 1});
    }
}

간선에는 용량이 존재하므로, 간선에 유량과 용량 정보를 같이 저장해야 한다. 간선이 저장하는 정보가 많으므로 이것들을 구조체로 묶기로 한다. 구조체에서 $v$는 반대쪽 정점의 번호, $\text{id}$는 반대쪽 정점의 인접 리스트에서 역방향 간선의 인덱스, $\text{flow}$와 $\text{cap}$은 각각 간선의 유량과 용량을 나타낸다. $u$와 $v$가 각각 소스, 싱크라고 하자.

struct H{int v, id, flow, cap;}
vector<H>e[1005];
int main()
{
    int m, n, s = 0, u, v, x, y, z;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, e[y].size(), 0, z});
        e[y].push_back({x, e[x].size() - 1, 0, 0});
    }
    cin >> u >> v;
}

다음으로 BFS로 증가 경로를 찾는 것을 구현한다. 잔여 유량이 있는 간선만 탐색하면 되는데, 증가 경로가 있을 경우 유량을 보내야 하므로 증가 경로 자체의 정보와 더 보낼 수 있는 데이터의 양도 저장해야 한다. 따라서 BFS를 실행하면서 각 정점마다 경로의 이전 정점($\text{pv}$, $\text{id}$)과 더 보낼 수 있는 데이터의 양($\text{flow}$)을 저장한다.

int pv[1005], id[1005], flow[1005];
queue<int>Q;

fill(pv + 1, pv + n + 1, -1);
fill(flow, flow + n + 1, 0);
flow[u] = 1 << 30; // 소스에서 소스로는 무한히 많은 유량을 보낼 수 있음
for(Q.push(u); pv[v] == -1 && Q.size(); Q.pop())
{
    int x = Q.front();
    for(auto &p: e[x])
    {
        int y = p.v;
        if(pv[y] == -1 && p.flow < p.cap)
        {
            pv[y] = x;
            id[y] = p.id;
            flow[y] = min(flow[x], p.cap - p.flow);
            Q.push(y);
        }
    }
}
for(; Q.size(); )Q.pop();

소스에서 싱크로 보낼 수 있는 유량이 존재한다면 유량을 보낸다.

if(flow[v])
{
    s += flow[v];
    for(int t=v; t!=u; t=pv[t])
    {
        e[pv[t]][pv[t][id[t]].id].flow += flow[v];
        e[t][id[t]].flow -= flow[v];
    }
}

이 과정을 더이상 유량을 보낼 수 없을 때까지 반복한다. 전체 코드는 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
struct H{int v, id, flow, cap;}
int pv[1005], id[1005], flow[1005];
vector<H>e[1005];
queue<int>Q;
int main()
{
    int m, n, s = 0, u, v, x, y, z;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, e[y].size(), 0, z});
        e[y].push_back({x, e[x].size() - 1, 0, 0});
    }
    cin >> u >> v;
    for(;;)
    {
        fill(pv + 1, pv + n + 1, -1);
        fill(flow, flow + n + 1, 0);
        flow[u] = 1 << 30;
        for(Q.push(u); pv[v] == -1 && Q.size(); Q.pop())
        {
            int x = Q.front();
            for(auto &p: e[x])
            {
                int y = p.v;
                if(pv[y] == -1 && p.flow < p.cap)
                {
                    pv[y] = x;
                    id[y] = p.id;
                    flow[y] = min(flow[x], p.cap - p.flow);
                    Q.push(y);
                }
            }
        }
        for(; Q.size(); )Q.pop();
        if(flow[v])
        {
            s += flow[v];
            for(int t=v; t!=u; t=pv[t])
            {
                e[pv[t]][pv[t][id[t]].id].flow += flow[v];
                e[t][id[t]].flow -= flow[v];
            }
        }
        else break;
    }
}

소스에서 싱크로 보낼 수 있는 최대 유량은 $s$가 된다.

 

[연습문제]

 

BOJ 17412. 도시 왕복하기 1 (Platinum IV)

간선의 용량을 전부 $1$로 두고 $1$번 정점에서 $2$번 정점까지의 최대 유량을 구한다.

 

BOJ 2367. 파티 (Platinum IV)

소스 - 사람 - 음식 - 싱크 순서로 그래프를 모델링한다. 소스에서 사람으로 가는 간선의 용량은 $K$이고, 사람에서 음식으로 가는 간선의 용량은 그 사람이 그 음식을 요리할 수 있으면 $1$, 아니면 $0$이다. 그리고 음식에서 싱크로 가는 간선의 용량은 그 음식을 가져올 수 있는 양의 제한이다.

 

BOJ 2316. 도시 왕복하기 2 (Platinum III)

$3$ ~ $N$번 도시를 나타내는 정점을 전부 둘로 분할한다. 그리고 한 정점에는 들어오는 간선을 연결하고, 다른 정점에는 나가는 간선을 연결한다. 또한 들어오는 정점에서 나가는 정점으로 가는 간선의 용량을 전부 $1$로 두면 최대 유량 문제가 된다. 이렇게 정점을 분할하는 방법도 때때로 사용되므로 알아 두면 좋다.