Introduction to Algorithm 4th edition을 번역 및 정리한 글입니다.

1. 에드먼즈-카프 알고리즘

포드-풀커슨 방법에서는 간선 및 정점 개수와 더불어, 최대 유량의 값에 따라서도 시간복잡도가 커질 수 있었다.

사실 포드-풀커슨 방법은 잔여 네트워크에서의 증가 경로를 찾을 수 없을 때까지 증가된 흐름을 흘려보내면 최대 유량을 찾을 수 있다는 것을 말할 뿐, 이를 어떻게 구현할지에 대해서는 구체적으로 말해주지 않는다. 포드-풀커슨 "알고리즘"이라는 용어보다, 포드-풀커슨 "방법"이라는 용어를 사용한 이유다.

에드먼즈-카프 알고리즘은 BFS를 통해 잔여 네트워크에서 $s \rightarrow t$ 최단 경로를 찾아, 그 경로를 증가 경로로 설정하는 알고리즘으로, 최대 유량의 값과 상관 없이 다항 시간 $O(|V||E|^2)$에 완료될 수 있다.

(1) 보조 정리들과 증명.

에드먼즈-카프 알고리즘이 다항 시간에 실행됨을 보이는 보조 정리들과 그 증명이다.

• $G = (V, E)$는 소스 $s$, 싱크 $t$를 가지는 유량 네트워크다.
• $\delta_f(u,v)$는 잔여 네트워크 $G_f$의 모든 간선이 1의 길이를 가지고 있다고 할 때, 정점 $u$에서 $v$까지의 최단 거리를 말한다.

Lemma 1

$G$에서 에드먼즈-카프 알고리즘을 실행할 때, 모든 정점 $v \in V - \{s, t\}$에 대해 매 유량 증가마다 잔여 네트워크 $G_f$에서의 최단 거리 $\delta_f(s,v)$는 단조 증가한다.

$pf.$
유량을 증가시켰을 때 소스 $s$에서 어떤 정점 $v \in V - \{s, t\}$로의 최단 거리가 더 짧아진다고 가정하고, 이것이 모순임을 보인다.

증가 직전의 유량을 $f$, 증가 직후의 유량을 $f'$라 하고, 유량 증가 이후 $s$로부터의 최단 거리가 감소한 정점들 중, 그 거리가 가장 짧은 정점을 $v$라 하자. $G_{f'}$에서 $s$를 출발해 $v$로 향하는 경로를 $p$라 하고, 이 경로에서 $v$ 바로 직전에 있는 정점을 $u$라고 하면 다음이 성립한다.

$v$가 유량 증가를 통해 $s$로부터의 최단 거리가 감소한 정점들 중 가장 짧은 거리를 가지는 정점이므로 $s$에서 $u$로의 최단 거리는 감소하지 않는다.
$\delta_{f'}(s, u) \geq \delta_f(s, u)$
$(u, v) \in E_f$라 해보자. 그러면

이므로, 유량 증가를 통해 최단 거리가 감소하지 않게 되어 모순이 발생한다. 따라서 $(u ,v) \not\in E_f$여야 한다.

Triangle Inequality
정점 $s$를 소스로 가지는, 가중치 함수 $w : E \rightarrow \mathbb{R}$을 가지는유향 그래프 $G = (V, E)$의 모든 간선 $(u, v) \in E$에 대해, $\delta(s, v) \leq \delta(s, u) + w(u, v)$이다.

$(u, v) \not\in E_f$이면서 $(u, v) \in E_{f'}$가 되는 경우는 $v$에서 $u$로의 유량이 흐르는 경우, 즉 $(v, u)$가 증가 경로에 포함되는 경우다.

에드먼즈-카프 알고리즘의 증가 경로는 $G_f$의 $s \rightarrow t$의 최단 경로고, 최단 경로의 부분 경로는 그 자체로도 최단 경로다. 따라서 이 증가 경로는 $s$에서 $u$로의 최단 경로를 포함하고 있으며, 이 경로($s$에서 $u$로의 최단 경로)의 마지막 간선은 $(v, u)$다. 그러므로

가 된다. 유량을 증가시켰을 때 $s$에서 $v$로의 최단 거리가 증가했으므로 또한 모순이 발생한다.

$(u, v) \in E_f$일 때에도, $(u, v) \not\in E_f$일 때에도 모순이므로 $\delta_{f'}(s, v) < \delta_f(s,v)$가 되는 $v$는 존재하지 않는다. 즉, 유량을 증가시켰을 때 최단 거리가 감소하는 일은 없다.

사실 $v \in V - \{s, t\}$만이 아니라, $v \in V$일 때에도 $\delta_f(s, v)$는 단조 증가한다.

1. $v=s$라면 증가 전후 모두 0임은 자명하다.
2. $v$가 $G_f$의 증가 경로 상 $t$ 바로 직전의 정점이라고 하면, $\delta_f(s, t) = \delta_f(s, v) + 1$이다. $\delta_f(s, v)$가 단조 증가하므로 $\delta_f(s, t)$도 단조 증가한다.

Lemma 2

$G$에서 에드먼즈-카프 알고리즘을 실행할 때 수행되는 유량 증가의 총 횟수는 $O(|V||E|)$다.

$pf.$
이전 글에서 봤듯, 다음을 만족하는 잔여 네트워크 $G_f$의 증가 경로 $p$ 위의 간선 $(u, v)$를 $p$의 핵심(critical) 간선이라 한다.

$|E|$개의 간선들 각각은 최대 $|V| / 2$번 핵심 간선이 될 수 있다.

모든 증가 경로에는 적어도 하나의 핵심 간선이 있으며, 증가 경로를 따라 유량을 증가시킬 때 해당 경로의 핵심 간선들은 잔여 네트워크에서 사라지게 된다.

$(u, v) \in E$인 정점 $u, v \in V$를 생각해보자. 증가 경로는 최단 경로이므로, $(u, v)$가 처음으로 핵심 간선이 되는 경우,

이 된다.

해당 증가 경로를 따라 유량을 증가시키면 $(u ,v)$는 잔여 네트워크에서 사라지게 되므로, $(u, v)$의 흐름이 감소하지 않는 한, 다르게 말하자면 $(v, u)$가 증가 경로에 나타나지 않는 한 이후 다른 증가 경로에서 나타날 수 없다.

$(v, u)$가 증가 경로에 나타났을 때 $G$의 유량을 $f'$라 하면,

이다.

Lemma 1에 따라 $s$에서 $v$로의 최단 거리는 단조 증가하므로

다.

즉 $(u, v)$가 처음으로 핵심 간선이 됐을 때부터, $(u, v)$가 다시 증가 경로에 포함될 수 있을 때까지 $s$에서 $u$까지의 최단 거리는 적어도 2는 증가하게 된다.

증가 경로는 $s \rightarrow t$의 최단 경로이므로 $(u, v)$가 증가 경로에 포함되어 있는 경우 $u \not= t$다. 따라서 잔여 네트워크에 $s \rightarrow u$ 경로가 포함되어 있다고 할 때, $s \rightarrow u$ 경로에는 최대 $|V| - 1$개의 정점, 최대 $|V| - 2$개의 간선이 포함될 수 있으므로 $\delta_f(u, v)$는 최대 $|V| - 2$다.

$\delta_f(s, u)$가 0에서 시작해 $(u, v)$가 증가 경로에 포함될 때마다 최소 2씩 늘어나, 최대 $|V| - 2$까지 증가할 수 있으므로, $(u, v)$는 많아야 $(|V| - 2) / 2 = |V|/2 -1$회 더 증가 경로에 포함될 수 있다. 즉 $(u, v)$는 맨 처음에 들어간 것까지 포함해 최대 $|V|/2$회 증가 경로에 포함될 수 있다.

잔여 네트워크의 간선 개수는 $O(|E|)$개고, 이 각각의 간선은 최대 $O(|V|)$번 증가 경로에 포함될 수 있으므로, 에드먼드-카프 알고리즘을 실행하면서 만나게 되는 핵심 간선의 개수는 $O(|V||E|)$개다.

모든 증가 경로는 적어도 하나의 핵심 간선을 포함하므로, 증가 경로의 개수, 즉 유량 증가의 횟수 또한 $O(|V||E|)$다.

Theorem

에드먼즈-카프 알고리즘의 시간복잡도는 $O(VE^2)$다.

$pf$
포드-풀커슨 방법에서 BFS를 통해 각 증가 경로를 찾는 데 걸리는 시간은 $O(|E|)$이다. 에드먼즈-카프 알고리즘에서 증가 경로의 개수는 최대 $O(|V||E|)$개이므로, 모든 증가 경로를 탐색하는 데 걸리는 총 시간은 $O(|V||E|^2)$다.

2. 코드 (C++)

백준 2367 파티의 소스 코드다. 이전 글에서 다뤘던 것과 같이 모델링을 해서 풀면 된다.

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

#define fastio cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(v) v.begin(), v.end()

const int INF = 1e9;

struct Flow_Network{
	vector<vector<int>> adj, capacity, flow;//인접리스트, 용량 행렬, 흐름 행렬
	vector<int> parent;//증가 경로 역추적을 위한 배열

	int source;
	int sink;

	Flow_Network(int N): source(0), sink(N + 1), capacity(N + 2, vector<int>(N + 2)), flow(N + 2, vector<int>(N + 2)), adj(N + 2), parent(N + 2) {}

	void add_edge(int from, int to, int c) {
		capacity[from][to] = c;
		adj[from].emplace_back(to);
		adj[to].emplace_back(from);//역방향 간선
	}

	bool find_augpath() {
		queue<int> q;
		q.push(source);

		fill(all(parent), -1);

		while (!q.empty()) {
			int from = q.front();
			q.pop();

			for (int to: adj[from]) {
				if (parent[to] != -1) continue;
				if (capacity[from][to] - flow[from][to] > 0) {
					parent[to] = from;
					q.push(to);
					if (to == sink) break;
				}
			}
		}

		return parent[sink] != -1;
	}


	int augment_flow() {
		int path_capacity = INF;//c_f(p)
		int ret = 0;

		for (int i = sink; i != source; i = parent[i]) {//증가 경로 상 최소 잔여 용량 간선 찾기
			int u = parent[i], v = i;
			int cf = capacity[u][v] - flow[u][v];//c_f(u, v)

			path_capacity = min(path_capacity, cf);
		}

		for (int i = sink; i != source; i = parent[i]) {//증가 경로로 유량 흘려보내기
			int u = parent[i], v = i;
			flow[u][v] += path_capacity;
			flow[v][u] -= path_capacity;
		}

		return path_capacity;//G_f에서 더 보낼 수 있는 유량 |f'|
	}

	int edmonds_karp() {
		int max_flow = 0;

		while (find_augpath()) max_flow += augment_flow();

		return max_flow;
	}
};

int main() {
	fastio;

	int N, K, D;
	cin >> N >> K >> D;

	Flow_Network network(N + D);

	for (int i = 1; i <= D; i++) {
		int M;
		cin >> M;
		network.add_edge(N + i, network.sink, M);
	}

	for (int i = 1; i <= N; i++) {
		network.add_edge(network.source, i, K);

		int Z;
		cin >> Z;

		for (int j = 0; j < Z; j++) {
			int food;
			cin >> food;
			network.add_edge(i, N + food, 1);
		}
	}

	cout << network.edmonds_karp();
}

모델링한 대로 유량 네트워크를 구성하고, 더 이상 증가 경로를 찾을 수 없을 때까지 증가 경로를 찾아 해당 경로로 흐름을 보내준다.

find_augpath에서는 BFS를 이용해 $s$에서 $t$로의 최단 경로를 찾는다. 이때 탐색 중 방문한 정점들의 경로를 역추적하기 위해 parent가 쓰인다. 만약 싱크까지의 경로가 존재한다면 추가로 흐름을 보낼 수 있다는 말이므로, 싱크에서부터 거꾸로 올라가면서 최소 잔여 용량을 찾아 그만큼을 경로에 흘려보내주고, 그렇지 않다면 더 이상 흘려보낼 수 없으므로 알고리즘을 종료한다.

여기서 flow에 담기는 값이 음수가 될 수도 있기는 하지만 문제는 없다. 현재의 흐름 $f$에 대한 잔여 네트워크 $G_f$에 포함될 간선이 어떤 것인지만 판단할 수 있으면 되기 때문이다. 간선의 capacity - flow가 양수면 해당 간선은 잔여 네트워크 $G_f$에 들어가게 된다.