[네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘

 

[네트워크 유량] Network Flow(최대 유량)

 

그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 합니다.

 

일단 해당 알고리즘에서 사용하는 용어부터 설명하겠습니다.

(네트워크 유량 알고리즘에서 간선은 두 정점을 잇는 파이프라고 생각하면 이해하기 쉽습니다.)

 

 

용량(Capacity)

 c(u, v)는 정점 u에서 v로 가는 간선의 용량(가중치)라고 합니다.

 

유량(Flow) 

f(u, v)는 정점 u에서 v로의 간선에 실제로 흐르는 유량을 의미합니다.

 

잔여 용량(Residual Capacity) 

간선의 용량과 유량의 차이를 의미합니다.  r(u, v) = c(u, v) - f(u, v)

즉, 해당 간선에 추가적으로 더 흘려 보낼 수 있는 유량입니다. 

 

소스(source)

유량이 시작되는 정점으로 모든 유량은 소스에서 부터 싱크로 흐르게 됩니다.

 

싱크(sink)

모든 유량이 도착하는 정점이 싱크입니다.

네트워크 유량 알고리즘은 소스에서 싱크로 흐를 수 있는 최대 유량을 계산합니다.

 

 

 

포드-풀커슨 & 에드몬드-카프 알고리즘(Ford-Fulkerson & Edmonds-Karp Algorithm)

 

네트워크 유량 알고리즘을 구현하는 비교적 간단한 방법입니다. 

이번에 설명하는 것은 포드-풀커슨의 네트워크 유량을 구하는 방법을 BFS로 구현한 알고리즘인 에드몬드-카프 알고리즘입니다.

(포드-풀커슨은 알고리즘이 아닌 방법만 제시했다고 하네요.)

 

 

포드-풀커슨 알고리즘은 모든 간선의 유량을 0으로 시작하여 소스에서 싱크로의 경로 중 유량을 늘릴 수 있는 경로를 찾아 유량을 흘려보내기를 반복합니다.

이때 유량을 흘려 보내기 위해 찾은 경로를 증가 경로(residual capacity)라고 합니다. 

증가 경로에 흐를 수 있는 유량은 경로에 포함되는 간선들의 잔여 용량 중 최솟값입니다.

(잔여 용량이 최소인 간선은 그 이상의 유량을 보내 줄 수 없기 때문입니다.)

 

이제 다음과 같은 그래프에서 증가 경로를 어떻게 찾아가는지 확인해 봅시다.

source: s, sink: t

 

해당 그래프의 최대 유량의 경로는 다음과 같지만

 

만약 s->a->b->t에 대한 경로가 먼저 찾아졌다면 s->b, a->t간선으로는 더 이상 유량을 보낼 수 없습니다.

이러한 문제를 해결하기 위해 유량의 대칭성이라는 속성이 있습니다.

유량의 대칭성이란 f(u, v) = -f(v, u)를 의미하는 것으로

u->v로 유량이 흘렀다면, 반대로 생각했을때 v에서는 u로 음수의 유량을 보내는 것이라 생각할 수 있습니다.

 

하지만 그래프에서 a->b방향의 간선은 있지만 b->a 방향의 간선은 없습니다.

따라서 b->a 방향에는 용량이 0인 유령 간선을 생성해 준다면 해당 간선에 흐를 수 있는 유량의 양인 잔여 유량은 다음과 같습니다.

r(v, u) = c(v, u) - f(v, u) = 0 - (-f(u, v)) = 0 -(-1) = 1

즉, 간선이 없는 역방향으로도 1의 유량을 흘려 보낼 수 있습니다!

 

그러므로 s->b->a->t 로의 새로운 증가 경로를 찾을 수 있습니다.

이 증가 경로의 유량은 최솟값인 b->a의 잔여 용량, 1입니다.

이때 b->a의 역방향인 a->b의 flow는 -1 감소하므로 결국 유량이 상쇄됩니다!

유량이 상쇄되더라도 소스에서 싱크로 가는 유량의 값은 변하지 않은 것을 확인할 수 있습니다.

 

 

 

 

에드몬드-카프 알고리즘 구현

 

이러한 포드-풀커슨 방법을 BFS로 구현한 에드몬드-카프 알고리즘을 확인해봅시다.

(가장 기본적인 포드-풀커슨 방법의 구현법이라 포드-풀커슨 알고리즘이라고도 부르는 듯합니다..)

 

간선들의 용량인 capacity[u][v]는 u에서 v로의 용량을 나타냅니다.

위의 유량의 대칭성을 구현해주기 위해 용량이 없는 간선들도 모두 0으로 초기화해줍시다.

 

간선들의 유량인 flow[u][v]는 u에서 v로의 간선에 실제로 흐르는 유량을 나타냅니다.

초기에는 어떠한 유량도 그래프에 흐르지 않으므로 0으로 초기화해 줍시다.

유량의 대칭성에서 확인했듯이 음수의 유량이 흐른다면 음수의 값을 저장해주면 되겠습니다.

 

 

이제 증가 경로를 찾는 방법입니다.

모든 유량은 항상 source에서부터 나오므로 source를 시작점으로 목적지인 sink까지의 최단 경로(가장 적은 간선을 거치는 경로)를 찾아 줍니다.

증가 경로를 찾는 방법에 DFS가 아닌 BFS를 이용하는 이유는 최악의 경우를 방지하기 위함으로 이후에 설명하겠습니다.

 

모든 라운드마다 source를 시작점으로 하는 BFS를 진행합니다.

이때 다음 정점(there)을 탐색하는 조건은 다음 정점으로의 간선에 잔여 용량이 남아 있는 경우입니다.

r(here, there) = capacity[here][there] - flow[here][there]

만약 해당 간선에 더 이상 잔여 용량이 없다면 더 이상 유량을 흘려보내 줄 수 없으므로 증가 경로에 포함될 수 없습니다.

 

다음 정점이 조건에 만족한다면 경로를 역추적하기 위해 here 정점을 there의 BFS 스패닝 트리의 부모로서 저장해줍니다.

parent[there] = here;

 

만약 방문한 정점(there)이 이미 부모가 있다면,  here보다 먼저 BFS 스패닝 트리에 포함된 것이므로 다시 방문하는 것은 최단 경로를 찾는데 의미가 없습니다.

(there이 here보다 depth가 같거나 낮으므로 다른 경로에서 there을 방문하는 편이 최단 경로이다.)

 

자, 이제 증가 경로를 찾았다면 해당 경로 상에서 가장 작은 잔여 용량이 새로 흘려줄 수 있는 유량(amount)입니다.

amount를 계산했다면 정방향은 flow를 amount 늘려주고

역방향은 대칭성에 의해 flow를 amount만큼 감소시켜 줍니다.

 

이러한 과정을 source에서 sink로의 경로 중 더 이상 유량을 흘려보낼 수 없을 때까지 반복해줍니다.

 

int capacity[MAXN][MAXN], flow[MAXN][MAXN];
 
//source: 시작 지점, sink: 목적 지점
int MaximumFlow(int source, int sink){
  memset(capacity, 0 , sizeof(capacity));
  memset(flow, 0, sizeof(flow));
  int total_flow;
 
  while(1){
    vector<int> parent(MAXN, -1);
    queue<int> q;
    parent[source] = source;
    q.push(source);
 
    //최단으로 sink로 도달하는 경로 찾기
    while(!q.empty() && parent[sink] == -1){
      int here = q.front();
      q.pop();
 
      for(int there =0; there<MAXN ; ++there)
        if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1){
          q.push(there);
          parent[there] = here;
        }
    }
 
    //sink까지의 경로를 못 찾았다면 더이상 증가 경로가 없음
    if(parent[sink] == -1)
      break;
 
    // 증가 경로로 새로 흘려줄 유량 = 경로 중 최소 잔여 용량
    int amount = INF;
    for(int p = sink ; p != source  ; p = parent[p])
      amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
    
    //증가 경로는 유량 증가, 역 방향 경로는 유량 감소
    for(int p = sink ; p != source  ; p = parent[p]){
      flow[parent[p]][p] += amount;
      flow[p][parent[p]] -= amount;
    }
 
    total_flow += amount;
  }
 
  return total_flow;
}

 

이러한 알고리즘은 경로를 찾는데 모든 정점(V)을 탐색해보고, 증가 경로는 최대 간선의 개수(E)만큼 존재할 수 있으므로

최단 경로를 찾는 BFS(O(logV))가 E번 반복됩니다.

따라서 시간 복잡도는 O(E*V)입니다.

 

 

BFS로 구현하는 이유

 

자, 이번에는 BFS로 구현하는 것이 왜 최적화에 중요한지 살펴봅시다.

만약 다음과 같은 그래프에서 DFS로 증가 경로를 찾아간다고 생각해봅시다.

 

 

s->a->b->t로의 경로를 증가 경로로 찾았다면 경로 중 최솟값인 1만이 새로운 유량으로 흐를 것입니다.

이제 DFS로 s->b->a->t의 경로를 찾았다면 이번에도 추가되는 유량은 1일 것입니다.

 

 

증가 경로를 찾는 과정은 source에서 sink로의 경로 중 더 이상 유량을 흘려보낼 수 없을 때까지이므로

s->a->b->t와 s->b->a->t의 경로가 번갈아 찾아지면서 최대 유량인 1000회 동안 반복됩니다.

 

하지만 BFS를 사용하면 source에서 sink로의 최단 경로만 찾으므로 이러한 예외가 발생하지 않습니다.

 

 

추가적으로 네트워크 유량(최대 유량)과 긴밀히 연관된 최소 컷 최대 유량 정리(Min-cut Max-flow Theorem)도 공부해 봅시다.

 

 

추천 문제

[백준] 최대 유량(6086) - 양방향 간선

 

 

 

참고 서적: 알고리즘 문제 해결 전략(구종만 저), 알고리즘 트레이닝(안티 라크소넨 저)

갓종만님.. 존경합니다...