최대 흐름 - Push-relabel 알고리즘¶
Push-relabel 알고리즘(선흐름-푸시 알고리즘이라고도 합니다)은 흐름 네트워크의 최대 흐름을 계산하는 알고리즘입니다. 우리가 풀고자 하는 문제의 정확한 정의는 최대 흐름 - Ford-Fulkerson과 Edmonds-Karp 글에서 찾을 수 있습니다.
이 글에서는 네트워크를 통해 선흐름(preflow)을 밀어 넣는 방식으로 문제를 해결하는 방법을 살펴봅니다. 이 방법은 $O(V^4)$, 더 정확하게는 $O(V^2 E)$ 시간에 동작합니다. 이 알고리즘은 1985년에 Andrew Goldberg와 Robert Tarjan이 고안했습니다.
정의¶
알고리즘을 수행하는 동안 우리는 선흐름(preflow), 즉 흐름 함수와 비슷하지만 흐름 보존 제약을 반드시 만족하지는 않는 함수 $f$를 다루어야 합니다. 선흐름에 대해서는 다음 제약
과
만 성립하면 됩니다.
따라서 어떤 정점은 내보내는 것보다 더 많은 흐름을 받을 수 있습니다. 이러한 정점은 초과 흐름을 가진다고 말하며, 그 양을 초과량(excess) 함수 $x(u) =\sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v))$로 정의합니다.
흐름 함수에서와 마찬가지로, 선흐름 함수로도 잔여 용량과 잔여 그래프를 정의할 수 있습니다.
알고리즘은 초기 선흐름(일부 정점이 초과량을 가짐)에서 시작하며, 실행 도중 선흐름을 다루고 수정합니다. 세부 사항을 미리 조금 밝히자면, 알고리즘은 초과량을 가진 정점을 하나 골라 그 초과량을 이웃 정점으로 밀어 냅니다. 알고리즘은 소스와 싱크를 제외한 모든 정점에 초과량이 없어질 때까지 이를 반복합니다. 초과량이 없는 선흐름이 올바른 흐름이라는 것은 쉽게 알 수 있습니다. 따라서 알고리즘은 실제 흐름을 얻은 상태로 종료됩니다.
하지만 아직 해결해야 할 문제가 두 가지 있습니다. 첫째, 이 과정이 실제로 종료된다는 것을 어떻게 보장할 수 있습니까? 둘째, 이 과정이 아무 흐름이 아니라 실제로 최대 흐름을 준다는 것을 어떻게 보장할 수 있습니까?
이 문제들을 해결하려면 또 다른 함수, 즉 각 정점에 정수를 부여하는 레이블링(labeling) 함수 $h$의 도움이 필요하며, 이 함수는 흔히 높이(height) 함수라고도 불립니다. $h(s) = |V|$, $h(t) = 0$이고, 잔여 그래프에 간선 $(u, v)$가 있을 때, 즉 간선 $(u, v)$가 잔여 그래프에서 양의 용량을 가질 때 $h(u) \le h(v) + 1$이면 레이블링이 올바르다고 합니다. 다시 말해, $u$에서 $v$로 흐름을 늘릴 수 있다면 $v$의 높이는 $u$의 높이보다 최대 1만큼만 작을 수 있으며, 같거나 오히려 더 높을 수도 있습니다.
올바른 레이블링 함수가 존재한다면 잔여 그래프에 $s$에서 $t$로 가는 증가 경로가 존재하지 않는다는 점에 유의하는 것이 중요합니다. 그러한 경로의 길이는 최대 $|V| - 1$개의 간선이고, 각 간선은 높이를 최대 1만큼만 낮출 수 있으므로, 첫 높이가 $h(s) = |V|$이고 마지막 높이가 $h(t) = 0$이라면 이는 불가능하기 때문입니다.
이 레이블링 함수를 사용하면 push-relabel 알고리즘의 전략을 다음과 같이 서술할 수 있습니다: 올바른 선흐름과 올바른 레이블링 함수에서 시작합니다. 각 단계에서 정점 사이로 초과량을 밀어 내고, 정점의 레이블을 갱신합니다. 각 단계가 끝난 뒤에도 선흐름과 레이블링이 여전히 올바르도록 보장해야 합니다. 그러면 알고리즘이 종료되었을 때 선흐름은 올바른 흐름입니다. 또한 올바른 레이블링도 가지고 있으므로 잔여 그래프에 $s$와 $t$ 사이의 경로가 존재하지 않으며, 이는 그 흐름이 실제로 최대 흐름이라는 것을 의미합니다.
Ford-Fulkerson 알고리즘과 push-relabel 알고리즘을 비교해 보면, 두 알고리즘은 서로 쌍대 관계에 있는 것처럼 보입니다. Ford-Fulkerson 알고리즘은 항상 유효한 흐름을 유지하면서 증가 경로가 더 이상 존재하지 않을 때까지 흐름을 개선하는 반면, push-relabel 알고리즘에서는 어느 시점에도 증가 경로가 존재하지 않으며, 선흐름(preflow)이 유효한 흐름이 될 때까지 선흐름을 개선합니다.
알고리즘¶
먼저 유효한 선흐름과 레이블링 함수로 그래프를 초기화해야 합니다.
Ford-Fulkerson 알고리즘에서처럼 빈 선흐름을 사용하는 것은 불가능합니다. 그렇게 하면 증가 경로가 존재하게 되고, 이는 유효한 레이블링이 존재하지 않음을 의미하기 때문입니다. 따라서 $s$에서 나가는 각 간선을 최대 용량으로 초기화합니다: $f((s, u)) = c((s, u))$. 그리고 나머지 모든 간선은 0으로 초기화합니다. 이 경우 유효한 레이블링이 존재하며, 소스 정점에는 $h(s) = |V|$, 나머지 모든 정점에는 $h(u) = 0$을 부여하는 레이블링이 바로 그것입니다.
이제 두 연산을 더 자세히 설명하겠습니다.
push 연산에서는 한 정점 $u$에서 이웃한 정점 $v$로 초과량 흐름을 최대한 많이 밀어 보내려고 합니다. 규칙은 하나입니다: $h(u) = h(v) + 1$인 경우에만 $u$에서 $v$로 흐름을 밀어 보낼 수 있습니다. 쉽게 말하면, 초과량 흐름은 아래쪽으로 흘러야 하지만 너무 가파르게 흘러서는 안 됩니다. 물론 밀어 보낼 수 있는 흐름은 $\min(x(u), c((u, v)) - f((u, v)))$뿐입니다.
어떤 정점에 초과량이 있지만 인접한 어떤 정점으로도 초과량을 밀어 보낼 수 없다면, 이 정점의 높이를 증가시켜야 합니다. 이 연산을 relabel이라고 부릅니다. 레이블링의 유효성을 유지하는 범위 내에서 가능한 한 많이 높이를 증가시킵니다.
요약하면, 알고리즘의 핵심은 다음과 같습니다: 유효한 선흐름과 유효한 레이블링을 초기화합니다. push 또는 relabel 연산을 수행할 수 있는 동안 이를 수행합니다. 그 후 선흐름은 실제로 흐름이 되며, 이를 반환합니다.
복잡도¶
정점의 최대 레이블이 $2|V| - 1$임은 쉽게 보일 수 있습니다. 이 시점에서 남아 있는 모든 초과량은 소스로 되돌려 보낼 수 있으며, 실제로 되돌려 보내집니다. 따라서 relabel 연산은 최대 $O(V^2)$번 수행됩니다.
또한 포화 push(간선의 전체 용량을 사용하는 push)는 최대 $O(V E)$번, 비포화 push(간선의 용량을 완전히 사용하지 않는 push)는 최대 $O(V^2 E)$번 수행됨을 보일 수 있습니다. 초과량이 있는 다음 정점을 $O(1)$ 시간에 찾을 수 있는 자료 구조를 선택하면, 알고리즘의 전체 복잡도는 $O(V^2 E)$입니다.
구현¶
const int inf = 1000000000;
int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess, seen;
queue<int> excess_vertices;
void push(int u, int v) {
int d = min(excess[u], capacity[u][v] - flow[u][v]);
flow[u][v] += d;
flow[v][u] -= d;
excess[u] -= d;
excess[v] += d;
if (d && excess[v] == d)
excess_vertices.push(v);
}
void relabel(int u) {
int d = inf;
for (int i = 0; i < n; i++) {
if (capacity[u][i] - flow[u][i] > 0)
d = min(d, height[i]);
}
if (d < inf)
height[u] = d + 1;
}
void discharge(int u) {
while (excess[u] > 0) {
if (seen[u] < n) {
int v = seen[u];
if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
push(u, v);
else
seen[u]++;
} else {
relabel(u);
seen[u] = 0;
}
}
}
int max_flow(int s, int t) {
height.assign(n, 0);
height[s] = n;
flow.assign(n, vector<int>(n, 0));
excess.assign(n, 0);
excess[s] = inf;
for (int i = 0; i < n; i++) {
if (i != s)
push(s, i);
}
seen.assign(n, 0);
while (!excess_vertices.empty()) {
int u = excess_vertices.front();
excess_vertices.pop();
if (u != s && u != t)
discharge(u);
}
int max_flow = 0;
for (int i = 0; i < n; i++)
max_flow += flow[i][t];
return max_flow;
}
여기서는 현재 초과량을 가진 모든 정점을 저장하기 위해 큐 excess_vertices를 사용합니다. 이렇게 하면 push 또는 relabel 연산을 수행할 다음 정점을 상수 시간에 선택할 수 있습니다.
그리고 흐름을 밀어 보낼 인접 정점을 찾는 데 너무 많은 시간을 쓰지 않도록 current-arc라는 자료 구조를 사용합니다. 기본적으로 간선들을 순환 순서로 순회하면서 마지막으로 사용한 간선을 항상 저장합니다. 이렇게 하면 특정 레이블링 값에 대해 현재 간선을 $O(n)$번만 바꾸게 됩니다. 그리고 relabel에 이미 $O(n)$ 시간이 걸리므로, 복잡도가 나빠지지 않습니다.