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

알고리즘에서의 네트워크 유량(Network Flow) 문제는 그래프에서 각 노드들 간의 용량(Capacity)이 정의되어 있을 시, 시작점(source)에서 끝점(target)까지 흐를 수 있는 최대 유량을 구하는 문제입니다.

이 네트워크 유량 문제를 해결하는 일반적으로 많이 쓰이는 방안으로는 크게 두 가지가 있습니다. 첫 번째는 DFS로 구현하는 포드 폴커슨 알고리즘(Ford-Fulkerson Algorithm), 두 번재는 BFS로 구현하는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm)이 있습니다. 여기서는 에드몬드 카프 알고리즘으로 네트워크 유량 문제를 푸는 방식과 구현 코드를 설명하도록 하겠습니다.

 위와 같이 용량에 대한 정보가 명시된 그래프에서, 1(source)에서 7(sink)까지의 최대 유량을 구하는 문제를 푸는 과정을 나타내 보겠습니다. 그 전에 알고리즘을 적용하기 전 알아야 될 용어 및 이 알고리즘을 이루는 속성에 대해서 설명하겠습니다.

1. 소스(S, source) : 시작점

2. 싱크(T, sink) : 끝점

3. 정점(Vertex) : 유량이 모이는 위치

4. 간선(Edge) : 유량이 흐르는 파이프 역할

5. 용량(Capacity) : 유량이 흐를 수 있는 크기

6. 유량(Flow) : 간선에 흐르는 현재 유량의 크기

7. 잔류 유량(Residual Flow) : Capacity - Flow로서 현재 간선에 흐를 수 있는 유량이 얼마나 인지를 나타냄

그리고, 용량과 유량은 다음과 같이 정의합니다.

1. c(u, v) : c는 Capacity를 의미, u에서 v로 흐를 수 있는 간선의 용량을 의미한다.

2. f(u, v) : f는 Flow를 의미하고, u에서 v로 흐른 실제 유량을 뜻한다.

1. 특정 경로를 따라 유량을 보낼 때는 그 경로에 포함된 간선 중 가장 용량이 작은 간선에 의해 결정된다.

=> 어떤 경로를 통해 유량을 보낼 때, 가장 용량이 작은 거에 맞춰 최대 용량이 결정된다는 소리입니다. 안 그러면 더 많은 유량을 보낼 시에는 파이프가 최대 용량을 벗어나 파이프가 터지겠죠.

2. 용량 제한 속성 : f(u,v) <= c(u,v) 

=> 흐르는 유량이 그 간선의 용량을 넘을 수 없습니다. 자명하죠

3. 유량의 대칭성 : f(u,v) = -f(v,u)

=> 이 알고리즘의 핵심 아이디어라고 생각합니다. u에서 v로 보낸 유량은 v에서 u의 역방향으로 보낸 유량과 의미상 같다는 것입니다. 이 개념은 알고리즘이 동작할 때 잔여 유량(residual flow)로서 기능하게 됩니다.

4. 나오는 유량과 들어오는 유량의 합은 항상 같아야 한다.

=> 자명한 이야기 입니다. 단 source와 sink는 예외입니다. 왜냐하면 sink는 받기만 하는 끝점이고 source는 나가기만 하는 시작점이기 때문이죠. 

위의 용어와 정리를 적용한 알고리즘의 동작 과정은 다음과 같습니다. 여기서 빨간색 화살표는 유량이 흐르는 간선을 나타내고 주황색 화살표는 정리2에서 설명은 유량의 대칭성에 의해 나타난 역방향 유량입니다. 1은 source고 7은 sink입니다.

먼저 BFS를 통해 source와 sink까지의 경로를 찾습니다.

다음 검색된 경로에서 현재 최소한의 유량이 흐를 수 있는 간선을 찾습니다. 그 다음 찾은 유량만큼 검색된 경로의 간선에 업데이트 합니다. (용량 정보에 업데이트 하는 것이죠)

다음 업데이트된 유량만큼 역방향 유량을 나타내는 간선도 업데이트 합니다. 그리고 이러한 과정을 더 이상의 잔류 유량(Capacity - Flow)이 남아있지 않을 때가지 반복합니다.

이 과정을 거치는 그래프의 상태를 나타내면 다음과 같습니다.

최종적으로 다음과 같은 상태로 알고리즘이 종료되게 됩니다.

아래는 네트워크 유량 문제를 푸는 에드몬드 카프 알고리즘을 구현한 예입니다. 코드가 상당히 많고 구현이 까다로운 편이지만 위의 알고리즘에 대한 내용이 머리 속에 박혀있으면 그리 어렵지는 않을 것입니다. ㅎㅎ;;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class NetworkFlow {

    public static int INF = 987654321;

    public static void main(String[] args) throws FileNotFoundException {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        int src = sc.nextInt();
        int sink = sc.nextInt();

        int[][] flow = new int[V+1][V+1];
        int[][] capacity = new int[V+1][V+1];
        boolean[][] adj = new boolean[V+1][V+1];

        for(int e = 0, a,b,c; e < E; ++e) {
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            capacity[a][b] = c;
            adj[a][b] = adj[b][a] = true;
        }

        Queue<Integer> q = new LinkedList<Integer>();
        int ans = 0;
        // Execute until there are no residual flow
        while(true) {
            int[] prev = new int[V+1];

            q.clear();
            q.add(src);
            prev[src] = src;

            //Find a path from source to target
            while(!q.isEmpty()) {
                int cur = q.poll();

                for(int there = 1; there <= V; ++there) {
                    if(!adj[cur][there]) continue;
                    if(prev[there] != 0) continue;

                    if(capacity[cur][there] - flow[cur][there] > 0) {
                        q.add(there);
                        prev[there] = cur;
                        if(there == sink) break;
                    }
                }
            }

            if(prev[sink] == 0) break;

            // Find the minimum residual flow
            int minFlow = INF;
            for(int v = sink; prev[v] != v; v = prev[v]) {
                minFlow = Math.min(minFlow, capacity[prev[v]][v] - flow[prev[v]][v]);
            }
            // Update the flow data and reverse flow data
            for(int v = sink; prev[v] != v; v = prev[v]) {
                flow[prev[v]][v] += minFlow;
                flow[v][prev[v]] -= minFlow;
            }

            ans += minFlow;
        }

        System.out.println(ans);
    }
}