Ford-Fulkerson algorithm
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
//네트워크 유량 문제를 해결하는 포드-폴커슨 알고리즘의 구현
const int INF = 987654321;
int V;
//capacity[u][v] : u에서 v로 보낼수 있는 용량
//flow[u][v] : u에서 v로 흘러가는 유량(반대 방향인 경우 음수)
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];
//flow[][]를 계산하고 총 유량을 반환한다
int networkFlow(int source, int sink)
{
//flow를 0으로 초기화한다
memset(flow, 0, sizeof(flow));
int totalFlow = 0;
while(true)
{
//너비 우선 탐색으로 증가 경로를 찾는다
vector<int> parent(MAX_V, -1);
queue<int> q;
parent[source] = source;
q.push(source);
while(!q.empty() && parent[sink] == -1)
{
int here = q.front(); q.pop();
for(int there = 0; there < V; ++there)
//잔여 용량이 남아 있는 간선을 따라 탐색한다.
if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1)
{
q.push(there);
parent[there] = here;
}
}
//증가 경로가 없으면 종료한다
if(parent[sink] == -1) break;
//증가 경로를 통해 유량을 얼마나 보낼지 결정한다
int amount = INF;
for(int p = sink; p != source; p = parent[p])
amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
//증가 경로를 통해 유량을 보낸다
for(int p = sink; p != source; p = parent[p])
{
flow[parent[p]][p] += amount;
flow[p][parent[p]] -= amount;
}
totalFlow += amount;
}
return totalFlow;
}
|
cs |
Ford-Fulkerson algorithm
네트워크 유량 알고리즘
증가 경로가 더이상 존재하지 않을 때까지 증가 경로를 찾고, 보낼 수 있는 최대 유량을 해당 경로를 따라 보내는 작업을 반복합니다.
증가경로는 잔여 용량이 남은 간선들만을 이용하는 BFS를 이옹해 찾습니다.
SOURCE -> SINK 의 경로를 찾았다면, 각 간선을 검사하면서 그중 최소 잔여 용량을 찾습니다. 이것이 이 경로를 따라 보낼 수 있는 최대 유량입니다.
그 후에는 각 간선의 유량을 갱신하는데, 유량의 대칭성을 유지하기 위해 한 방향의 유량을 늘리면 다른 방향의 유량은 줄여줍니다!
Min-cut Max-flow Theorem
cut : source와 sink가 다른 집합에 속하도록 그래프의 정점들을 두 개의 집합으로 나눈것
source가 속한 집합 : S
sink가 속한 집합 : T
컷 S,T의 용량 : S->T로 가는 간선들의 용량 합
컷 S,T의 유량 : S->T로 실제로 보내는 총 유량
속성
1. 컷의 유량은 source->sink로 가는 총 유량과 같다
2. 컷의 유량은 용량과 같거나 더 작다
네트워크에 용량과 유량이 같은 컷 S`, T`가 존재하면, S`, T`는 항상 최소 컷이며, 현재 소스에서 싱크로 보내는 유량은 네트워크의 최대 유량입니다.
인접 리스트로 Ford-Fulkerson algorithm 구현하기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
//인접 리스트로 포드-폴커슨 알고리즘 구현하기
//간선의 정보를 나타내는 구조체
struct Edge
{
int target, capacity, flow;
//역방향 간선의 포인터
Edge* reverse;
//이 간선의 잔여 용량을 계산한다
int residualCapacity() const
{
return capacity - flow;
}
//이 간선을 따라 용량 amt를 보낸다
void push(int amt)
{
flow += amt;
reverse->flow -= amt;
}
};
//유량 네트워크의 인접 리스트
vector<Edge*> adj[MAX_V];
//u에서 v로 가는 간선을 추가한다
void addEdge(int u, int v, int capacity)
{
Edge* uv = new Edge(), *vu = new Edge();
//u에서 v로 가는 간선을 초기화한다
uv->target = v;
uv->capacity = capacity;
uv->flow = 0;
uv->reverse = vu;
//v에서 u로 가는 간선을 초기화한다. 이 간선의 용량은 0이다
vu->target = u;
vu->capacity = 0;
vu->flow = 0;
vu->reverse = uv;
adj[u].push_back(uv);
adj[v].push_back(vu);
}
|
cs |
각 단방향 간선 (u, v)마다 용량이 0인 유령간선(v, u)를 네트워크에 추가해 줘야 합니다.
이 유령 간선은 유량을 상쇄하는 데만 사용합니다.
각 간선의 유령간선에 빠르게 접근하기 위해 서로를 가르키는 포인터를 가지고 있습니다.
시간복잡도
f : 최대 유량
O(|E|f) 와 O(|V||E|^2)중 작은것