에드몬드-카프 알고리즘
에드몬드-카프 알고리즘(Edmonds-Karp algorithm) 에서는 경로를 이루는 간선의 개수가 최소가 되도록 경로를 선택한다. 깊이 우선 탐색 대신 너비 우선 탐색을 이용하면 그러한 경로를 찾을 수 있다. 이 경우 유량이 빠르게 증가한다는 것을 증명할 수 있으며, 알고리즘의 시간 복잡도는 이 된다.
while BFS로 S→T 경로를 찾을 수 있으면:
그 경로의 병목 용량을 구한다.
그만큼 유량을 보낸다.1. 잔여 그래프를 만든다.
2. BFS로 source → sink까지 갈 수 있는 가장 짧은 증강 경로를 찾는다.
3. 그 경로에서 보낼 수 있는 최대 유량 amount를 구한다.
4. 정방향 간선 cap은 줄이고, 역방향 간선 cap은 늘린다.
5. 더 이상 sink까지 갈 수 없으면 종료한다.시간 복잡도
Edmonds-Karp는 항상 BFS 최단 증강 경로를 선택하기 때문에, Ford-Fulkerson의 최악 사례처럼 특정 병목 간선을 반복해서 사용하려 해도, 그 간선이 다시 병목으로 등장할 때마다 BFS 레벨이 증가한다. 따라서 같은 간선을 무한정 반복해서 사용할 수 없다.
V: 같은 간선이 병목으로 다시 등장할 수 있는 최대 횟수E: 병목 후보 간선 개수E: 매번 BFS로 증강 경로를 찾는 비용
요약
- Ford-Fulkerson에서 증가 경로를 찾을 때 BFS를 사용하도록 고정한 알고리즘 이다.
- 즉, 간선 개수가 가장 적은
S → T증가 경로를 매번 선택한다. - 찾은 경로의 최소 잔여 용량만큼 유량을 흘리고 잔여 그래프를 갱신한다.
- BFS를 사용해서 경로 선택이 안정적이며 용량 크기에 크게 영향을 받지 않는다.
- 시간복잡도는 이다.
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
struct Edge {
int to; // 도착 정점
int rev; // 반대 방향 간선의 위치
ll cap; // 현재 남은 용량, 즉 잔여 용량
};
class EdmondsKarp {
private:
int n;
vector<vector<Edge>> graph;
// 현재 잔여 그래프에서, 간선 수가 가장 적은 증강 경로(유량을 보낼 수 있는 경로)를 찾기
bool bfs(
int source,
int sink,
vector<int>& parentNode,
vector<int>& parentEdge
) {
fill(parentNode.begin(), parentNode.end(), -1);
fill(parentEdge.begin(), parentEdge.end(), -1);
queue<int> q;
q.push(source);
parentNode[source] = source;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < (int)graph[cur].size(); i++) {
Edge& e = graph[cur][i];
// 잔여 용량이 없는 간선은 사용할 수 없음 || 이미 방문한 정점은 다시 방문하지 않음
if (e.cap <= 0 || parentNode[e.to] != -1) continue;
parentNode[e.to] = cur;
parentEdge[e.to] = i;
if (e.to == sink) {
return true;
}
q.push(e.to);
}
}
return false;
}
public:
EdmondsKarp(int n) : n(n), graph(n) {}
void addEdge(int from, int to, ll cap) {
// {from, to: 반대 간선의 위치, cap}
Edge forward = {to, (int)graph[to].size(), cap};
Edge backward = {from, (int)graph[from].size(), 0};
graph[from].push_back(forward);
graph[to].push_back(backward);
}
ll maxFlow(int source, int sink) {
if (source == sink) return 0;
ll totalFlow = 0;
vector<int> parentNode(n);
vector<int> parentEdge(n);
// while 반복 회수 O(V * E)
// bfs 시간 복잡도 (E)
while (bfs(source, sink, parentNode, parentEdge)) {
// 증강 경로 위의 최소 잔여 용량 찾기
ll amount = INF;
for (int v = sink; v != source; v = parentNode[v]) {
int u = parentNode[v];
int edgeIndex = parentEdge[v];
amount = min(amount, graph[u][edgeIndex].cap);
}
// 경로 위의 정방향 간선은 감소,
// 역방향 간선은 증가
for (int v = sink; v != source; v = parentNode[v]) {
int u = parentNode[v];
int edgeIndex = parentEdge[v];
Edge& e = graph[u][edgeIndex];
e.cap -= amount;
graph[e.to][e.rev].cap += amount;
}
totalFlow += amount;
}
return totalFlow;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
EdmondsKarp ek(n);
for (int i = 0; i < m; i++) {
int from, to;
ll cap;
cin >> from >> to >> cap;
from--;
to--;
ek.addEdge(from, to, cap);
}
int source, sink;
cin >> source >> sink;
source--;
sink--;
cout << ek.maxFlow(source, sink) << '\n';
return 0;
}python
from collections import deque
INF = 10**18
class EdmondsKarp:
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)
def max_flow(self, source, sink):
total_flow = 0
# O(V * E)
while True:
parent_node = [-1] * self.n
parent_edge = [-1] * self.n
q = deque([source])
parent_node[source] = source
# BFS: 가장 짧은 증강 경로 찾기 O(E)
while q and parent_node[sink] == -1:
u = q.popleft()
for i, edge in enumerate(self.graph[u]):
v, rev, cap = edge
if cap <= 0 or parent_node[v] != -1:
continue
parent_node[v] = u
parent_edge[v] = i
q.append(v)
if v == sink:
break
# 더 이상 증강 경로가 없음
if parent_node[sink] == -1:
break
# 증강 경로의 최소 잔여 용량
amount = INF
v = sink
while v != source:
u = parent_node[v]
i = parent_edge[v]
amount = min(amount, self.graph[u][i][2])
v = u
# 유량 보내기
v = sink
while v != source:
u = parent_node[v]
i = parent_edge[v]
edge = self.graph[u][i]
to, rev, _ = edge
edge[2] -= amount
self.graph[to][rev][2] += amount
v = u
total_flow += amount
return total_flow
ek = EdmondsKarp(6)
ek.add_edge(0, 1, 12) # 1 -> 2
ek.add_edge(0, 3, 11) # 1 -> 4
ek.add_edge(1, 2, 6) # 2 -> 3
ek.add_edge(1, 3, 3) # 2 -> 4
ek.add_edge(1, 4, 5) # 2 -> 5
ek.add_edge(1, 5, 9) # 2 -> 6
ek.add_edge(2, 5, 8) # 3 -> 6
ek.add_edge(3, 4, 9) # 4 -> 5
ek.add_edge(4, 2, 3) # 5 -> 3
ek.add_edge(4, 5, 4) # 5 -> 6
source = 0 # 1번 정점
sink = 5 # 6번 정점
print(ek.max_flow(source, sink))
"""
# 입력 예시
n, m = map(int, input().split())
ek = EdmondsKarp(n)
for _ in range(m):
u, v, cap = map(int, input().split())
u -= 1
v -= 1
ek.add_edge(u, v, cap)
source, sink = map(int, input().split())
print(ek.max_flow(source - 1, sink - 1))
"""