최대 유량 문제

참고 : 알고리즘 문제 해결 전략 - 구종만

 

최대 유량 문제 : 네트워크 상에서 엣지에 보낼 수 있는 용량이 정해져 있을 때, 어떻게 하면 source에서 sink로 최대로 유량을 보낼 수 있는가에 대한 문제 

 

기본적인 최대 유량 문제 해결을 위한 알고리즘

- Ford-Fulkerson, Edmonds-Karp, Dinic 알고리즘

 

Ford-Fulkerson : source에서 sink로 보낼 수 있는 최대 유량을 보낼 수 있는 경로를 계속 찾는 방식 (exponetial하든 polytime이든 상관없이 첫 아이디어 관점이지만, 대부분 이에 기초한 방식을 사용)

Edmonds-Karp : Ford-Fulkerson 알고리즘에서 최대 유량 보낼 수 있는 경로를 bfs 기반으로 찾음 

(bfs 기반으로 찾을 때 최대 유량 보내는 경로 찾는데 O(VE) 만큼임이 증명됨.) 

(참고 : https://koosaga.com/133)

Dinic : DFS, BFS 섞어서 사용한 방식 (아직 이거는 공부 안 해서 추후 다시 정리)

 

복잡도 : (참고 : https://koosaga.com/18)

dfs : O(fE) (f : 최대 유량)

bfs : O(min(fE, VE^2))

dinic : O(min(fE, V^2E)) ( cap이 0,1로 unit인 경우, O(min(V^(2/3), E^(1/2))) )

 

유량 네트워크 속성

u -> v 엣지 용량 c(u, v), 실제 흐르는 유량 f(u, v) (capacity, flow)

1. 용량 제한 : f(u, v) <= c(u, v) : 유량은 용량을 초과할 수 없다.

2. 유량 대칭성 : f(u, v) = -f(v, u) : u에서 v로 유량이 흐르는 것은, v의 입장에서 음수만큼 u로 유량을 보내는 것

3. 유량 보존 : sum of f(u, v) for all v linked to u = 0 : u와 연결된 모든 v로의 유량의 합은 0 이다.

이는 유량의 대칭성에 의해 실제로 연결은 안 되어 있지만, 가상으로 연결된 모든 노드를 대상으로 한 것이다.

즉, 들어온 유량과 나가는 유량의 합은 동일하다. 

 

source : 네트워크에서 유량이 시작되는 지점

sink : 네트워크에서 유량이 도착하는 지점

source, sink에서는 유량 보존이 성립되지 않는다. (들어오거나 나가는게 없으므로) 

 

---

 

Ford Fulkerson 알고리즘

 

동작 원리 : 유량 네트워크 모든 엣지의 유량을 0으로 시작하여, source에서 sink로 유량을 더 보낼 수 있는 경로를 찾아 이를 반복

 

증가 경로 (augmenting path) : 유량을 보내는 경로

유량을 보낼 수 있다. : 엣지에 이미 흐르고 있는 유량 외에 추가로 보낼 수 있는 여유 용량이 필요하다. 

잔여 용량 (residual capacity) : 엣지의 용량과 유량의 차이 ( r(u, v) = c(u, v) - f(u, v) )

 

증가 경로를 통해 흘려 보낼 수 있는 유량의 최대량 = 경로에 포함된 엣지의 잔여 용량 중 가장 작은 값

(가장 작은값보다 큰 값을 보내면 해당 경로 상에 그 값만큼 못 보내는 구간 존재) 

 

Ford Fulkerson 알고리즘 : 증가 경로가 더 이상 존재하지 않을 때까지 증가 경로를 찾고, 보낼 수 있는 최대 유량을 해당 경로를 따라 보내는 작업을 반복

 

ex. s : source, t : sink

       

s --> a ( cap 1)  --> t (cap 2)

         |   (cap 1)

        v 

  --> b  (cap 3)  --> (cap 1) 

 

위와 같은 상황에서 s에서 t로 가는 증가 경로를 처음에 s -> a -> t 로 잡으면 (증가 경로) 보낼 수 있는 최대 유량은 1 이고

s-> b -> t 로 잡으면 (증가 경로) 보낼 수 있는 최대 유량은 1 이다. 

 

따라서 해당 그래프의 최대 유량은 2이다. 

 

그런데 위 예에서 s -> a -> b -> t 를 처음 증가 경로로 잡으면 1의 flow가 a -> b 사이에 이미 흐르게 되어, s -> a / s-> b에 대해 추가 경로를 설정하지 못한다. 

 

이 때 사용되는 것이 유량의 대칭성이다. 가상의 b -> a (cap 0) 가 있다고 하자. 

먼저 선택된 s -> a -> b -> t 증가 경로로 a -> b에 flow 1이 계산되면, b의 입장에서는 -1만큼 flow가 흐른 것이므로,

잔여 용량은 0 - (-1) = 1 이다. 

즉, b -> a 로 1만큼 가상의 잔여 용량이 생기게 되며, 이는 a->b 의 유량을 그 만큼 상쇄하게 된다. 

따라서 가상의 새 잔여 용량만큼 유량을 보내는 것과 기존의 유량을 상쇄하는 것은 동일한 연산이다. 

 

그러므로 s->a->b->t 로 처음 증가 경로를 잡더라도, 이후 s->b->a->t 경로 (b->a : 가상의 경로) 를 통해 유량을 계산하는 것과

s->a->t, s->b->t 로 계산하는 것이 동일하게 되어 최대 유량을 구할 수 있게 된다. 

 

---

 

Ford Fulkerson + BFS (Edmonds Karp) 구현

 

위 예시를 그대로 적용하면 아래와 같다. 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// graph : source -> a (1), a -> sink (2)
// source -> b (3), b -> sink (1)
// a -> b (1) 
// (x) : cap = x

int inf = 987654321;
int v = 4; // source 0, a 1, b 2, sink 3
int cap[4][4]; // u->v cap
int flow[4][4]; // u->v flow

vector<int> graph[4]; // [u] = {v0, v1, ...} (가상의 역방향 포함) (가상 역방향의 cap은 0)

void init() {
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 3};
    graph[3] = {1, 2};

    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            cap[i][j] = 0;
            flow[i][j] = 0;
        }
    }

    cap[0][1] = 1;
    cap[0][2] = 3;
    cap[1][2] = 1;
    cap[1][3] = 2;
    cap[2][3] = 1;

    // 최대 유량은 2 
}

int edmond_karp(int source, int sink) {

    int res = 0; // 최대 유량 

    while(true) {
        vector<int> parent(4, -1); // 증가 경로 상의 부모 노드 저장용 
        queue<int> q; // bfs로 증가 경로 찾기 위함
        parent[source] = source;
        q.push(source);

        while(!q.empty() && parent[sink] == -1) {
            int cur = q.front();
            q.pop();

            for(auto next : graph[cur]) {
                // 잔여 용량 남아 있고, 아직 증가 경로에 포함 안 된 경우
                // 현재 탐색 중인 증가 경로에 포함 
                if(cap[cur][next] - flow[cur][next] > 0 && parent[next] == -1) {
                    q.push(next);
                    parent[next] = cur;
                }
            }
        }

        // 더 이상 증가 경로 없는 경우
        if(parent[sink] == -1) break;

        // 증가 경로를 통해 flow 얼마나 보낼 지 결정
        // 잔여 용량 (cap - flow) 중 최소값만큼 보낼 수 있음
        int minReserve = inf;
        int p; // parent node
        for(int node = sink; node != source; node = parent[node]) {
            p = parent[node];
            minReserve = min(minReserve, cap[p][node] - flow[p][node]);
        }

        // 증가 경로로 유량 보냄 (받는 쪽은 음수 처리)
        for(int node = sink; node != source; node = parent[node]) {
            p = parent[node];
            flow[p][node] += minReserve;
            flow[node][p] -= minReserve;
        }

        // 전체 유량에 추가 
        res += minReserve;
    }

    return res;
}

int main() {
    init();

    int res = edmond_karp(0, 3);
    cout << res;
}