네트워크 플로우(Network Flow)

  네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다. 이러한 알고리즘은 교통 체증, 네트워크 데이터 전송 등의 다양한 분야에 활용되고 있다.

 

 

  표현 방식은 유량(Flow)/용량(Capacity)이다.  즉 1에서 2로 가는길은 12명이 갈 수 있는 용량에 실제로는 0명이 가게 되었다는 소리이다.

 

  이제 간단하게 하나의 간선으로 용량과 용량을 표현해보면, 위와 같이 A에서 B로 갈 수 있는 용량은 8, B에서 C로 갈수 있는 용량은 6, C에서 D로 갈 수 있는 용량은 7이라고 해보자. 이때 A에서 D로 최대한 많은 용량을 보내려고 할 때 가장 합리적인 양은 얼마일까?

 

  바로 6이다. 바로 이러한 문제를 해결하는 핵심 알고리즘이 네트워크 플로우 알고리즘이다. 일반적으로 이를 최대 유량(Max Flow) 문제라고 정의한다.

 

  즉, 최대 유량 문제는 각 간선에 정해진 용량이 있을 때 A에서 B로 최대로 보낼 수 있는 유량의 크기를 구하는 문제이다.

---

 

  이제 한 번 여러 개의 정점과 간선이 있는 그래프를 보자

 

  기본적으로 최대 유량 문제는 단순하게 가능한 모든 경우의 수를 탐색하는 방법을 사용한다. 이 때 BFS을 이용하는 것이 일반적이다. 이것을 에드몬드 카프(Edmonds-Karp) 알고리즘이라고 한다.

 

  가능한 모든 경우의 수를 탐색하기 위해 기본적으로 위와 같이 현재 흐로고 있는 유량(Flow)을 모두 0으로 설정한다. 이후 정해진 용량(Capacity) 안에서 가능한 용량의 양을 반복적으로 더해주면 된다.

 

  이제 얼핏 보면 더이상 보낼 수 있는 방법이 없는 것처럼 보인다. 이제 여기에 최대 유량 알고리즘의 핵심적인 부분이 등장한다. 바로 음의 유량을 계산하는 것이다. 우리가 단순하게 유량을 더해주는 과정에서 사실은 보이지 않게 반대로 가는 유량이 빼지고 있다고 봐야 한다.

 

  2에서 3으로 6만큼 흐로고 있다는 것은 사실 3에서 2로 -6만큼 흐르고 있다고 볼 수 있다. 물론 실제로는 불가능한 이야기이므로 용량은 6이고 유량이 -6인 것처럼 기록됩니다. 이러한 기억을 하는 이유는 바로 남아있는 모든 가능한 경로를 더 찾아내기 위해서 입니다. 이렇게 음의 유량을 기록하게 해주게 되면 다음과 같이 새로운 경로를 찾을 수 있습니다.

 

 

  1 -> 4 -> 5 -> 3-> 2 -> 6이다. 이렇게 해주게 되면 1만큼의 유량을 더 보낼 수 있다. 대신 여기에서 기억해야 할 점은 2 -> 3으로 가는 유량에서는 1을 역으로 빼주셔야 한다는 것이다. 즉, 최대 유량 알고리즘은 이렇게 음의 유량도 고려해서 모든 경우의 수를 찾아줄 때 최적의 해를 찾을 수 있다.

 

  다른 경우는 존재하지 않으므로 결과적으로 위 예시에서 정점 6으로 도달하는 최대 유량은 19이다.

 

  최대 유량 알고리즘은 순서가 상관 없다. 남아있는 양이 1이 넘으면 계속해서 흘러보내주면 알아서 최적화가 이루어진다는 점에서 특별한 상황이 아니면 유량을 보내는 순서를 고려할 필요가 없다.

 

  기본적으로 BFS를 사용해서 모든 가능한 경로를 다 찾아서 남아있는 용량만큼 유량을 흘려 보내주는 것을 반복하면 된다. 그 과정에서 앞서 설명한 대로 음읭 유량도 함께 처리를 해주기만 하면 된다.

 

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

#define MAX 100
#define INF 100000000

using namespace std;

int n = 6, result;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> a[MAX];

void maxFlow(int start, int end) {
	while(1) {
		fill(d, d + MAX, -1);
		queue<int> q;
		q.push(start);
		
		while(!q.empty()) {
			int x = q.front();
			q.pop();
			
			for(int i = 0; i < a[x].size(); i++) {
				int y = a[x][i];
				// 방문하지 않은 노드 중에서 용량이 남은 경우
				if(c[x][y] - f[x][y] > 0 && d[y] == -1) {
					q.push(y);
					d[y] = x; // 경로를 기억합니다.
					if(y == end) break; // 도착지에 도달을 한 경우.
				}
			}
		}
		// 모든 경로를 다 찾은 뒤에 탈출합니다.
		if(d[end] == -1) break;
		int flow = INF;
		// 거꾸로 최소 유량 탐색합니다.
		for(int i = end; i != start; i = d[i]) {
			flow = min(flow, c[d[i]][i] - f[d[i]][i]);
		}
		// 최소 유량 만큼 추가 합니다.
		for(int i = end; i != start; i = d[i]) {
			f[d[i]][i] += flow;
			f[i][d[i]] -= flow;
		}
		result += flow;
	}
}

int main(void) {
	a[1].push_back(2);
	a[2].push_back(1);
	c[1][2] = 12;
	
	a[1].push_back(4);
	a[4].push_back(1);
	c[1][4] = 11;
	
	a[2].push_back(3);
	a[3].push_back(2);
	c[2][3] = 6;
	
	a[2].push_back(4);
	a[4].push_back(2);
	c[2][4] = 3;
	
	a[2].push_back(5);
	a[5].push_back(2);
	c[2][5] = 5;
	
	a[2].push_back(6);
	a[6].push_back(2);
	c[2][6] = 9;
	
	a[3].push_back(6);
	a[6].push_back(3);
	c[3][6] = 8;
	
	a[4].push_back(5);
	a[5].push_back(4);
	c[4][5]= 9;
	
	a[5].push_back(3);
	a[3].push_back(5);
	c[5][3] = 3;
	
	a[5].push_back(6);
	a[6].push_back(5);
	c[5][6] = 4;
	
	maxFlow(1, 6);
	printf("%d", result);
}

 

  BFS를 이용하는 에드몬드 카프 알고리즘의 경우 시간 복잡도가 O(VE^2)이다.