최소 비용으로 유량을 보내는 경우를 찾는 문제

이 글에서 최단 경로는 항상 '최소 비용인 경로'를 뜻한다.

이 글은 (링크)를 읽고 이해한 것을 바탕으로 엄밀한 증명들을 다소 생략하고 간략히 작성하였다.

알고리즘

입력 : 구하는 유량의 상한 $M$, 음수 사이클이 없는 유량 네트워크 $(G,c,a,s,t)$ : 각각 (그래프, 용량, 비용, 소스, 싱크)
출력 : $M$ 이하의 최대 유량, 최소 비용

1. 모든 간선 $e$의 유량을 0으로 한다 : $f(e) \gets 0$
2. $\mathbf{val}(f) < M$이고, $G_f$에서, $s$에서 $t$로 가는 경로가 있다면 아래를 반복한다.
   • a. $s$에서 $t$로 가는 최단 경로 $P$를 구한다.
   • b. $P$에 0보다 큰 유량을 흘려보낸다. 이를 $\vartriangle f$라고 하자.
   • c. $f \gets f + \vartriangle f$
3. return $f$

정리 1.

$G$ 상의 가능한 두 flow $f$와 $f'$의 덧셈, 뺄셈은 다음과 같이 정의된다.
$G$의 모든 간선 $e$에 대해
$(f' \pm f)(e) = f'(e) \pm f(e)$

$\mathbf{val} (f)$ : 소스에서 싱크로 흐르는 유량.
$\mathbf{cost} (f)$ : $f$에 대한 비용.
이들은 음수가 될 수도 있다.

이때, 다음을 만족한다.
$\mathbf{val} (f' \pm f) = \mathbf{val} (f') \pm \mathbf{val} (f)$
$\mathbf{cost} (f'\pm f) = \mathbf{cost} (f') \pm \mathbf{cost} (f)$

정리 2.

$(G,c,a,s,t)$는 음수 사이클이 없는 네트워크이다. 이때, $f$가 $\mathbf{val} (f)$인 flow 중 최소 비용이라면, $G_f$에는 음수 사이클이 없다. 이는 필요 충분 조건으로, $G_f$에 음수 사이클이 없다면 $f$는 최소 비용이다.

증명 : $f$가 최소 비용이면 $G_f$에 음수 사이클이 없다.

간단한 증명은 아래와 같다.

다른 방법으로도 증명할 수 있다.
$f$가 $\mathbf{val} (f)$ 중 최소 비용이고 $G_f$에 음수 사이클이 존재한다고 가정해보자. $G_f$에 있는 음수 사이클에만 유량을 흘려 보내 flow $g$를 얻을 수 있다. 이때, 다음을 만족한다.
$\mathbf{val} (g) = 0$
$\mathbf{cost} (g) < 0$

따라서,
$\mathbf{val} (f) = \mathbf{val} (f+g)$
$\mathbf{cost} (f+g) < \mathbf{cost} (f)$

이는 $f$가 $\mathbf{val} (f)$ 중 최소 비용이라는 것과 모순되므로 $G_f$에 음수 사이클이 존재할 수 없다.

증명 : $G_f$에 음수 사이클이 없으면 $f$는 최소 비용이다.

최소 비용이 아닌 flow $f'$을 가정해보자. 따라서 다음을 만족하는 $f$가 존재한다.
$\mathbf{val} (f') = \mathbf{val} (f)$
$\mathbf{cost} (f') > \mathbf{cost} (f)$
$G_{f'}$에 value가 $0$이고 비용이 음수인 경로, 즉 음수 사이클이 존재해야만 $f$가 존재할 수 있다. $f'$에 음수 사이클이 없다면 $f$가 존재할 수 없고, $f'$이 최소 비용이 아니라는 것과 모순이다.

정리 3.

알고리즘 진행 중 구하는 $G_f$의 최단 경로의 길이는 줄어들지 않는다.

증명

알고리즘 진행 중 얻어진 flow $f$가 있다. 또한,
$G_f$에서 최단 경로인 $P$를 구하고 $\gamma > 0$만큼 유량을 흘려보내 flow $g$를 얻었다. 이후,
$G_g$에서 최단 경로인 $Q$를 구하고 $\delta > 0$만큼 유량을 흘려보내 flow $h$를 얻었다.

$Q$의 비용이 $P$의 비용보다 작다고 가정해보자. $G_f$에서 $P$에 $\gamma\frac{\gamma}{\gamma+\delta}$만큼의 유량을 흘려 보내고, $Q$에 $\delta\frac{\gamma}{\gamma+\delta}$ 만큼의 유량을 흘려 보내자. $P$가 $Q$에 영향을 끼친다고 해도, $P$에 원래의 $\frac{\gamma}{\gamma+\delta}$ 만큼 유량을 보냈기 때문에 $Q$에도 원래의 $\frac{\gamma}{\gamma+\delta}$ 만큼은 유량을 보낼 수 있을 것이다. 이것을 flow $g'$이라고 하자. 이때, 다음을 만족한다.
$\mathbf{val} (g'-f) = \mathbf{val} (g-f) = \gamma$
$\mathbf{cost} (g'-f) < \mathbf{cost} (g-f)$
이는 $g$가 $G_f$상에서 최소 비용이라는 것과 모순이다. 따라서 $Q$의 비용이 $P$의 비용보다 작아질 수 없다.

따라서 알고리즘 수행 도중 얻어진 $(G,c,a,s,t)$의 최소 비용은 다음과 같다. $M$은 최대 유량이다.

물론 cost가 음수로 내려가지 않을 수도 있다.

Dinic, Dijkstra, Potential을 사용한 MCF

알고리즘

입력 : 음수 사이클이 없는 유량 네트워크 $(G,c,a,s,t)$
출력 : $M$ 이하의 최대 유량, 최소 비용

1. 모든 간선 $e$의 유량을 0으로 한다 : $f(e) \gets 0$
2. Bellman-Ford로 potential 계산
3. $\mathbf{val}(f) < M$이고, $G_f$에서, $s$에서 $t$로 가는 경로가 있다면 아래를 반복한다.
   • a. Dijkstra와 potential을 이용하여 shortest-path subgraph인 $S$를 구한다. 동시에 다음 potential을 계산한다.
   • b. $S$에서 Dinic 알고리즘을 수행한다.
4. return $f$

Potential

potential은 그래프에서 음수 간선을 없애고 다익스트라 알고리즘을 사용할 수 있게 해준다. 이를 위해 $p$ 함수를 다음과 같이 mapping하자.

$p: V \to \mathbb{R}$

$u$에서 $v$로 향하는 간선 $e$의 비용 $a(e)$이 있을 때, $a_p(e)$를 다음과 같이 정의할 수 있다.
$a_p(e) = p(u) + a(e) - p(v)$

새로 정의한 비용인 $a_p$을 적용하여 경로 $u_0u_1...u_k$의 비용을 다음과 같이 구할 수 있다.
$∑^k_{i=1}a_p(e_i)$
$=∑^k_{i=1}(a(e_i)+p(u_{i−1})−p(u_i))$
$=∑^k_{i=1}a(e_i)+∑^{k−1}_{i=0}p(u_i)−∑^k_{i=1}p(u_i)$
$=∑^k_{i=1}a(e_i)+p(u_0)−p(u_k)$

이는 곧, 기존 비용 + (출발점과 도착점의 $p$값 차이)와 같다.

$p$ 함수를 다음과 같이 정의하자.
$p(v)$ : $G_f$에서, $s$에서 정점 $v$까지의 최단 경로의 길이
이러면 모든 $e$에 대해 $a_p(e) \ge 0$를 만족한다. 이러한 $p$를 potential이라고 부른다.

• 증명

  정점 $u$에서 $v$로 향하는 간선을 $e$라고 하자. $p(u)$와 $p(v)$가 각각 $s$ to $u$의 최단 거리, $s$ to $v$의 최단 거리이므로, $p(u) + a(e) \ge p(v)$ (이)가 성립한다. 즉, $p(u) + a(e) - p(v) \ge 0$ 이다.

최단 경로 상의 $a_p$값은 항상 0이다.

$p$값의 갱신

알고리즘을 수행하면서 $p$값은 계속 바뀐다. 이 또한 다익스트라로 계산할 수 있다. $G_f$에서 $s$ to $u$의 최단 경로의 길이를 $x$라고 하자. $p(s)=0$ 이므로, $p$를 이용한 $s$ to $v$ 최단 경로의 길이는 $x-p(u)$가 된다. 새로운 $p$값은 $x$가 되야 하므로, $x-p(u)$에 자기 자신인 $p(u)$를 더해 만들 수 있다. $p(u)$의 최댓값은 간선의 비용의 최댓값 $C$에 정점의 개수 $n$을 곱한 $nC$이다.

시간 복잡도

(3번 과정의) 한 반복에서 유량은 최소 1 증가한다. 유량이 1 증가할 때, Dinic알고리즘이 수행되는 데 걸리는 시간은 $O(E)$이고, 다익스트라는 $O(E\log E)$시간이 걸린다. 매 반복마다 유량이 1씩만 증가한다면, 최대 유량인 $F$ ($F \le M$)만큼 반복할 것이다. 이때 시간 복잡도는 $O(FE\log E)$이다.

한 반복에서 유량이 2 이상 증가하는 경우가 있을 땐 계산이 매우 복잡해진다. 이때, 증가하는 유량을 $f$라고 할 때, Dinic 알고리즘의 수행 시간은 $(O(VE*\min(f,V)))$이다. 간단히 $O(V^2E)$라고 하자. 또한, 반복 횟수의 상한은 최단 경로의 길이의 최댓값 $K$, 혹은 $F$ 중 작은 것이다. 따라서 전체 시간 복잡도는 $O(V^2E*\min(F,K))$이다.
$K$는 $nC$로 간단하게 계산할 수 있다. $n$은 정점의 개수이고, $C$는 한 간선이 가질 수 있는 비용의 최댓값이다.

간단히 $O(V^2EF)$라고 생각하면 될 것 같다. 하지만 실제로는 이보다 빠를 것이다. (체감상 $O(FE\log E)$ 보다 빠르다.)

구현

#include <vector>
#include <queue>
using namespace std;

const int MAXV = 802, INF=987654321;
int capacity[MAXV][MAXV], flow[MAXV][MAXV], cost[MAXV][MAXV];

vector<int> edge[MAXV], work, level, p;

// 음수 사이클이 있을 경우 텅 빈 배열을 반환
vector<int> CalcDist_BellmanFord(int n_vertex, int source, int sink) {
	vector<int> upper(n_vertex, INF);
	upper[source] = 0;
	bool updated;

	for (int iter = 0; iter < n_vertex; iter++) {
		updated = false;
		for (int u = 0; u < n_vertex; u++) {
			for (int v : edge[u]) {
				// (u, v) 간선을 따라 완화를 시도한다.
				if (upper[v] > upper[u] + cost[u][v]) {
					upper[v] = upper[u] + cost[u][v];
					updated = true;
				}
			}
		}
		if (!updated) break;
	}

	if (updated) upper.clear();
	return upper;
}

bool CalcDist_Dijkstra(int n_vertex, int source, int sink) {
	vector<int> next_p = p, shortest(n_vertex,INF);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	shortest[source] = 0;
	pq.push({ shortest[source],source });
	while (!pq.empty()) {
		int dist_u = pq.top().first;
		int u = pq.top().second;
		pq.pop();
		if (shortest[u] < dist_u) continue;

		for (int v : edge[u]) {
			if (capacity[u][v] - flow[u][v] <= 0) continue;

			int dist_v = dist_u + p[u] + cost[u][v] - p[v];
			if (dist_v < shortest[v]) {
				shortest[v] = dist_v;
				pq.push({ dist_v,v });
			}
		}
		next_p[u] = shortest[u] + p[u];
	}
	p = next_p;
	return shortest[sink] < INF;
}

bool BFS(int n_vertex, int source, int sink) {
	level = vector<int>(n_vertex, -1);

	queue<int> q;
	level[source] = 0;
	q.push(source);

	while (!q.empty()) {
		int u = q.front();   q.pop();
		for (int v : edge[u])
			if (level[v] == -1 && capacity[u][v] - flow[u][v] > 0 && p[u] + cost[u][v] - p[v] == 0) {
				level[v] = level[u] + 1;
				q.push(v);
			}
	}
	return level[sink] != -1;
}

int DFS(int u, int get, int sink, int& this_cost) {
	if (u == sink)
		return get;

	for (int& i = work[u]; i < edge[u].size(); i++) {
		int v = edge[u][i];
		int residue = capacity[u][v] - flow[u][v];
		if (level[v] == level[u] + 1 && residue > 0 && p[u] + cost[u][v] - p[v] == 0) {
			int put = DFS(v, min(get, residue), sink, this_cost);
			if (put > 0) {
				this_cost += cost[u][v];
				flow[u][v] += put;
				flow[v][u] -= put;
				return put;
			}
		}
	}
	return 0;
}

pair<int,int> MCF_Dinic(int n_vertex, int max_flow, int source, int sink) {
	p = CalcDist_BellmanFord(n_vertex,source,sink);
	if(p.empty()) return {-1,0}; // 음수 사이클이 존재함

	int total_flow = 0, total_cost=0;
	while (max_flow > 0 && CalcDist_Dijkstra(n_vertex, source, sink)) {
		while (max_flow > 0 && BFS(n_vertex, source, sink)) {
			work = vector<int>(n_vertex, 0);
			while (max_flow > 0) {
				int this_cost = 0;
				int put = DFS(source, max_flow, sink, this_cost);
				if (put == 0)break;
				max_flow-=put;
				total_flow += put;
				total_cost += this_cost * put;
			}
		}
	}
	return { total_flow,total_cost };
}

void Connect(const int u, const int v, const int _capacity, const int _cost) {
	edge[u].push_back(v);
	edge[v].push_back(u);
	capacity[u][v] = _capacity;
	cost[u][v] = _cost;
	cost[v][u] = -_cost;
}

Reference

• -is-this-fft-'s blog