네트워크플로우, 에드몬드 카프(Edmonds-Karp) 알고리즘

BFS를 이용하여 네트워크플로우 source에서 sink까지 흘러들어가는 총 유량을 구할 수 있는 에드몬드 카프(Edmonds-Karp) 알고리즘

정점 A에서 B로 들어가는 간선은 E(A,B) 로 표현하면, 간선은 용량(capacity), 유량(flow) 값을 가진다. 

유량을 구현하지 위해서는 3가지 조건이 충족되어야 한다.

    1) 유량 제한 속성

        C(A,B) - F(A,B) >= 0

    2) 유량 대칭성

        F(A,B) = -F(B,A)

    3) 유량 보존

        유량을 흘려보내는 시작점 source, 유량의 도착지 sink 를 제외한 정점에서의 들어오는 유량과 나가는 유량은 같아야한다. 즉, 들어오는 유량 == 나가는 유량 이어야 한다.

이러한 3가지 조건을 충족해서 유량을 흘려보내야한다.

아래 그림으로 해당 조건을 지키고 있는지 볼 수 있다. 

source는 들어오는 간선이 없고, sink는 나가는 간선이 없다. 나머지 노드또한 그러할 수 있으나, 흘러오는 유량이 없다면 나가는 유량도 없으므로 유량보존을 시킬 수 있다.

임의적으로 유량을 흘려보낸다고 하자. 만약에 아래와 같은 식으로 유량이 흘러간다면,

source->1->sink 로 가는 길을 막게 된다. 이를 해결하기 위해서 유량의 대칭성을 이용할 수 있다.

아래 그림과 같이 유량의 대칭성을 이용하여 F(2,1) = -F(1,2) 로 유량이 들어왔다는 표시를 할 수 있다. 이때 다른 간선에도 유량의 대칭성이 표시되어야 하지만 설명에는 정점 1과 2를 잇는 간선의 유량이 중요하므로 다른 유량의 대칭성으로 인한 역간선은 추가하지 않았다.

이렇게 대칭성으로 만들어진 F(1,2) 의 유량은 아래와 같이 이용될 수 있다. C(1,2) - F(1,2) = 0 - (-2) > 0 이므로 2의 유량을 흘려보낼 수 있음을 알 수 있다. 대칭성으로 이러한 방법이 만들어진다.

source -> 1 -> sink 로 가는 길이 없어졌지만, 역간선을 이용하여  source -> 1 -> 2 -> sink로 유량을 흘려보낼 수 있음을 볼 수 있다.

이렇게 유량을 모두 흘려보내게 되면, 아래와 같이 sink에 총 4의 유량을 흘려보낼 수 있다.

이런 성질을 이용하여 BFS를 이용한 에드몬드 카프 알고리즘을 구현할 수 있다. 

아래는 코드이다.

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int MAX_V = 111;
const int INF = 1 << 30;
 
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int parent[MAX_V];
 
int residual(int here, int there) {
    return c[here][there] - f[here][there];
}
 
int min2(int a, int b) {
    return (a > b) ? b : a;
}
 
int edmonds_karp(int source, int sink) {
    int total = 0;
    while (true) {
        memset(parent, -1, sizeof(parent));
        queue<int> Q;
        Q.push(source);
        parent[source] = source;
        while (!Q.empty() && parent[sink] == -1) {
            int here = Q.front();
            Q.pop();
            for (int there = 0; there < MAX_V; there++) {
                if (residual(here, there) > 0 && parent[there] == -1) { 
                    parent[there] = here;
                    Q.push(there);
                }
            }
        }
        
        if (parent[sink] == -1) break;
 
        int mn = INF;
        for (int p = sink; p != source; p = parent[p]) {
            mn = min2(c[parent[p]][p] - f[parent[p]][p], mn);
        }
 
        for (int p = sink; p != source; p = parent[p]) {
            f[parent[p]][p] += mn;
            f[p][parent[p]] -= mn;
        }
        total += mn;
    }
    return total;
}