포드-풀커슨 알고리즘
포드-풀커슨 알고리즘(Ford-Fulkerson algorithm) 은 그래프의 최대 유량을 찾는 알고리즘이다. 유량이 0인 상태에서 알고리즘을 시작하고, 단계마다 소스에서 싱크로 가는 경로 중 유량을 늘릴 수 있는 경로(증강 경로, augmenting path)를 찾는다. 더는 유량을 늘릴 수 없을 때의 값이 최대 유량이 된다.
이 알고리즘에서는 간선마다 반대 방향의 간선도 추가한 형태의 특별한 그래프 표현을 사용한다. 각 간선의 가중치는 유량을 얼마나 늘릴 수 있는지를 나타낸다. 알고리즘의 시작 단계에서는 원래 간선의 가중치를 간선의 용량과 동일하게 두고, 반대 방향 간선의 가중치를 0으로 둔다. 그림 20에 예제 그래프에 대한 표현이 나와 있다.
- 반대 간선은 이미 보낸 유량을 나중에 취소하거나 재조정하기 위해 잔여 그래프에 추가하는 가상 간선
포드-풀커슨 알고리즘은 여러 라운드로 구성되어 있다. 라운드마다 소스에서 싱크로 가는 경로 중 모든 간선의 가중치가 양수인 경로를 찾는다. 그러한 경로가 여러 가지라면 어떤 것을 선택해도 된다. 선택한 경로에 포함된 간선의 가중치 최솟값이 라면 유량을 만큼 증가시킬 수 있다. 이를 위해 경로 상의 각 간선에 대해 그 가중치를 만큼 감소시키고, 반대 방향 간선의 가중치를 만큼 증가시킨다.
- 그림 20. 포드-풀커슨 알고리즘에서 사용하는 그래프 표현
이 알고리즘에서 사용된 아이디어는 간선의 유량이 증가하면 앞으로 추가할 수 있는 유량은 감소한다는 데 바탕을 두고 있다. 알고리즘을 진행하면서 다른 경로를 택하는 것이 더 유리한 상황임을 알게 되었다면, 역으로 반대 방향 간선을 이용하여 기존의 유량을 감소시키는 것도 가능하다. 소스에서 가중치가 양수인 간선을 이용하여 싱크로 가는 경로가 존재하는 동안 이 알고리즘을 계속 반복한다. 만일 그러한 경로가 존재하지 않는다면 최대 유량을 구한 것이며, 알고리즘은 종료한다.
그림 21에 포드-풀커슨 알고리즘을 이용하여 예제 그래프의 최대 유량을 찾는 과정이 나와 있다. 알고리즘은 네 번의 라운드로 진행된다. 첫 번째 라운드에서는 경로 을 선택한다. 이 경로상의 최소 가중치는 2이므로 유량이 2만큼 증가한다. 다음으로 경로를 세 번 더 선택한 뒤, 유량을 각각 3, 1, 1만큼 증가시킨다. 그 다음에는 가중치가 양수인 간선으로 구성된 경로가 없고, 최대 유량은 이 된다.
- 그림 21. 포드-풀커슨 알고리즘
시간 복잡도
S ──M──> A ──M──> T
\ │
M 1
\ ↓
───> B ──M──> T- DFS가
S→A→B→T를 고르면 병목이A→B의 1이라 유량이 +1만 증가. - 이때
A→B는 0이 되고, 역방향B→A가 1로 열린다. - 다음 DFS가
S→B→A→T를 고르면 다시 병목이 1이라 +1. B→A를 사용했으므로 기존A→B유량이 취소되어A→B가 다시 1로 살아난다.- 이후
A→B, B→A를 번갈아 사용하면서 최대 유량이 계속 1씩 증가할 수 있다. - 최대 유량이 F라면 최악에 증강을
O(F)번 수행한다. - 증강 경로 탐색 한 번이
O(E)이므로 Ford-Fulkerson은 정수 용량에서O(EF).
요약
- 시작점
S에서 도착점T까지 잔여 용량이 있는 경로 를 하나 찾는다. - 그 경로에서 가장 작은 잔여 용량만큼 유량을 흘린다.
- 사용한 만큼 정방향 용량을 줄이고, 역방향 간선의 잔여 용량을 늘린다.
- 더 이상
S → T경로를 찾을 수 없을 때까지 반복한다. - 경로 탐색 방식에 따라 성능이 달라지며, 정수 용량이면 보통
O(EF)로 본다.F = maxflow
cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;
struct Edge {
int to; // 도착점
int rev; // 역방향 간선 인덱스
ll cap; // 잔여 용량
};
class FordFulkerson {
private:
int n;
vector<vector<Edge>> graph;
// DFS로 하나의 증강 경로 찾기
ll dfs(int u, int sink, ll flow, vector<bool>& visited) {
if (u == sink)
return flow;
visited[u] = true;
for (auto& edge : graph[u]) {
int v = edge.to;
int rev = edge.rev;
ll cap = edge.cap;
// 잔여 용량이 없거나 이미 방문한 정점이면 무시
if (cap <= 0 || visited[v])
continue;
// 현재 경로에서 보낼 수 있는 최대 유량
ll amount = dfs(
v,
sink,
min(flow, cap),
visited
);
// sink까지 도달했다면 유량 갱신
if (amount > 0) {
// 정방향 잔여 용량 감소
edge.cap -= amount;
// 역방향 잔여 용량 증가
graph[v][rev].cap += amount;
return amount;
}
}
return 0;
}
public:
FordFulkerson(int n)
: n(n), graph(n) {}
void add_edge(int u, int v, ll cap) {
Edge forward = {
v,
(int)graph[v].size(),
cap
};
Edge backward = {
u,
(int)graph[u].size(),
0
};
graph[u].push_back(forward);
graph[v].push_back(backward);
}
ll max_flow(int source, int sink) {
ll total_flow = 0;
while (true) {
vector<bool> visited(n, false);
// DFS로 하나의 증강 경로 탐색
ll amount = dfs(
source,
sink,
INF,
visited
);
// 더 이상 증강 경로가 없음
if (amount == 0)
break;
total_flow += amount;
}
return total_flow;
}
};
int main() {
// --------------------------------------------------
// 테스트 그래프
// --------------------------------------------------
int n = 6;
struct InputEdge {
int u, v;
ll cap;
};
vector<InputEdge> edges = {
{0, 1, 12}, // 1 -> 2
{0, 3, 11}, // 1 -> 4
{1, 2, 6}, // 2 -> 3
{1, 3, 3}, // 2 -> 4
{1, 4, 5}, // 2 -> 5
{1, 5, 9}, // 2 -> 6
{2, 5, 8}, // 3 -> 6
{3, 4, 9}, // 4 -> 5
{4, 2, 3}, // 5 -> 3
{4, 5, 4}, // 5 -> 6
};
int source = 0;
int sink = 5;
FordFulkerson ff(n);
for (auto [u, v, cap] : edges) {
ff.add_edge(u, v, cap);
}
cout << ff.max_flow(source, sink) << '\n';
}python
import sys
sys.setrecursionlimit(10**6)
INF = 10**18
class FordFulkerson:
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, u, v, cap):
# edge = [도착점, 역방향 간선 인덱스, 잔여 용량]
forward = [v, len(self.graph[v]), cap]
backward = [u, len(self.graph[u]), 0]
self.graph[u].append(forward)
self.graph[v].append(backward)
# DFS로 하나의 증강 경로 찾기
def dfs(self, u, sink, flow, visited):
if u == sink:
return flow
visited[u] = True
for edge in self.graph[u]:
v, rev, cap = edge
# 잔여 용량이 없거나 이미 방문한 정점이면 무시
if cap <= 0 or visited[v]:
continue
# 현재 경로에서 보낼 수 있는 최대 유량
amount = self.dfs(
v,
sink,
min(flow, cap),
visited
)
# sink까지 도달했다면 유량 갱신
if amount > 0:
# 정방향 잔여 용량 감소
edge[2] -= amount
# 역방향 잔여 용량 증가
self.graph[v][rev][2] += amount
return amount
return 0
def max_flow(self, source, sink):
total_flow = 0
while True:
visited = [False] * self.n
# DFS로 하나의 증강 경로 탐색
amount = self.dfs(
source,
sink,
INF,
visited
)
# 더 이상 증강 경로가 없음
if amount == 0:
break
total_flow += amount
return total_flow
# --------------------------------------------------
# 테스트 그래프
# --------------------------------------------------
n = 6
edges = [
(0, 1, 12), # 1 -> 2
(0, 3, 11), # 1 -> 4
(1, 2, 6), # 2 -> 3
(1, 3, 3), # 2 -> 4
(1, 4, 5), # 2 -> 5
(1, 5, 9), # 2 -> 6
(2, 5, 8), # 3 -> 6
(3, 4, 9), # 4 -> 5
(4, 2, 3), # 5 -> 3
(4, 5, 4), # 5 -> 6
]
source = 0
sink = 5
ff = FordFulkerson(n)
for u, v, cap in edges:
ff.add_edge(u, v, cap)
print(ff.max_flow(source, sink))