Ford-Fulkerson Algorithm & Edmons-Karp Algorithm
2020-1νκΈ°, λνμμ βμκ³ λ¦¬μ¦β μμ μ λ£κ³ 곡λΆν λ°λ₯Ό μ 리ν κΈμ λλ€. μ§μ μ μΈμ λ νμμ λλ€ :) μ 체 ν¬μ€νΈλ Algorithm ν¬μ€νΈμμ νμΈνμ€ μ μμ΅λλ€.
μ΄λ² ν¬μ€νΈλ Network Flow ν¬μ€νΈμ νμ ν¬μ€νΈμ λλ€. Network Flow λ¬Έμ μ ν΅μ¬μ΄ λλ μ λ¦¬μΈ <Max-Flow Min-Cut Theorem>μ λν΄ κΆκΈνλ€λ©΄ μ΄μ ν¬μ€νΈλ₯Ό μ°Έκ³ ν΄μ£ΌμΈμ! π
μ΄λ² ν¬μ€νΈμ μ½λλ λ°±μ€ 6086λ²: μ΅λ μ λ λ¬Έμ λ₯Ό κΈ°μ€μΌλ‘ μμ±λμμ΅λλ€ π¨βπ»
Network Flow ν¬μ€νΈμμ μ΄λ»κ² Max Flowλ₯Ό ꡬν μ§ <Max-Flow Min-Cut Theorem>μ ν΅ν΄ μ΄ν΄λ³΄μλ€. μ΄λ² ν¬μ€νΈμμλ Residual Graphλ₯Ό μ¬μ©νλ ν΄λΉ μκ³ λ¦¬μ¦μ μ§μ ꡬνν΄λ³Έλ€.
Ford-Fulkerson Algorithm
μ¬μ€ Network Flow ν¬μ€νΈμμ μ€λͺ ν Max-Flowλ₯Ό μ°Ύλ λ°©λ²μ μ½λλ‘ κ΅¬νν κ²μ λΆκ³Όνλ€. ν° λ²μ£Όλ‘ λ΄€μ λλ Brute Force Algorithmμ μνλ€.
1. sourceμμ sinkλ‘ κ°λ μ λμ λ³΄λΌ μ μλ κ²½λ‘ $p$λ₯Ό νλ μ°Ύλλ€. DFS λλ BFSλ₯Ό μ΄μ©νλ©΄ λλ€.
2. μ°ΎμλΈ κ²½λ‘ $p$λ‘ λ³΄λΌ μ μλ μ΅λνμ μ λμ ꡬνλ€. μ΅λνμ μ λμ κ²½λ‘ $p$λ₯Ό νμ(traversal)νλ©° κ°μ₯ μμ λ¨μ capacityκ° λλ€.
3. μ°ΎμλΈ κ²½λ‘ $p$μ μ΅λ μ λμ μ€μ λ‘ νλ €λ³΄λΈλ€. μ΄ κ³Όμ μμ μλ°©ν₯μ μ λμ μΆκ°νκ³ , μλ°©ν₯μ μ λμ λΊλ€.
μλ₯Ό λ€μ΄ μ°ΎμλΈ κ²½λ‘ $p$κ° $a \rightarrow b \rightarrow c$λΌλ©΄,
// μλ°©ν₯
f(a, b) += flow
f(b, c) += flow
// μλ°©ν₯
f(b, a) -= flow
f(c, b) -= flow
μ£Όλͺ©ν μ μ [3.] κ³Όμ μμ μλ°©ν₯μ μ²λ¦¬ν λμΈλ°, λ§μ½ $f(b, a) = 0$μ΄μλ€λ©΄ $f(b, a) < 0$λ‘ μμκ° λλ€. κ·Έλ°λ° μ΄λ° μμ μ λμ νλ €λ³΄λ΄λ κ²μ κ°λ₯νλ°, $f(b, a)$μ capacityλ $c(b, a) = 0$μ΄λ―λ‘ κ²°κ΅ $f(b, a) < 0 = c(b, a)$λ‘ μ λμ λν λ²μΉμ μ ν κΉ¨λ¨λ¦¬μ§ μλλ€!
μ½λλ‘ μμ±νκΈ° μ μ μμΌλ‘ μ΄ μκ³ λ¦¬μ¦μ λ°λΌκ°λ³΄μ. μ΄ λΆλΆμ μ’μ μλ£κ° μμ΄μ ν΄λΉ μλ£λ‘ λ체νκ² λ€. π μμΌλ‘ νΈλ Ford-Fulkerson Algorithm
μ΄μ μ½λλ‘ μ΄ν΄λ³΄μ.
β¨ Tip: μ΄ λ¬Έμ μ κ²½μ° κ·Έλνλ₯Ό Adjacency List 보λ€λ Adjacency Matrixλ‘ νννλκ² μκ³ λ¦¬μ¦μ μ§κΈ° ν¨μ¬ νΈν΄μ§λ€! π
λ¨Όμ λ¬Έμ μ μ
λ ₯μ 보면, λ
Έλκ° Alphabet λμλ¬Έμλ‘ λ€μ΄μ¨λ€. λ³ΈμΈμ μλ¬Έμλ‘λ λ€μ΄μ¨λ€λ κ±Έ λμ€μ κΉ¨λ¬μλ€ π± μ
λ ₯μ μ κ·ννκΈ° μν΄μ 'A'
λ‘ λΉΌμ£Όλ©΄ λλ€. κ·Έλ¬λ©΄ λ
Έλλ [A-Z]: [0, 26], [a-z]: [32, 57]
μ λ²νΈλ₯Ό κ°κ² λλ€.
μ°λ¦¬λ int capacity[][]
λΌλ λ°°μ΄μ νμ΄νμ νλ₯Ό μ μλ μ λμ capacityλ₯Ό κΈ°λ‘νλ€. κ·Έλμ μ
λ ₯μ ν΅ν΄ Graphλ₯Ό ꡬμΆνλ©΄ μλμ κ°λ€.
#define MAX 80
int capacity[MAX][MAX];
for (int i = 0; i < N; i++) {
char s, e;
int c;
cin >> s >> e >> c;
capacity[s - 'A'][e - 'A'] += c;
capacity[e - 'A'][s - 'A'] += c;
}
μ΄μ μ€λΉλ λλ¬κ³ , 본격μ μΌλ‘ <\Ford-Fulkerson Algorithm>μ ꡬνν΄λ³΄μ.
long long FordFulkerson(int source, int sink) {
long long ret = 0;
// find path and update residual graph
while (1) {
...
// dfs
while (!s.empty()) {
...
}
// escape: no possible path
if (Prev[sink] == -1) break;
// find possible max-flow
// flow the max-flow
total_flow += flow;
}
return total_flow;
}
λ¨Όμ dfs ꡬν λΆλΆμ μ΄ν΄λ³΄μ.
int Prev[MAX];
fill(Prev, Prev + MAX, -1);
Prev[source] = source;
stack<int> s;
s.push(source);
// dfs
while (!s.empty()) {
int curr = s.top();
s.pop();
if(curr == sink) break;
for (int i = 0; i < MAX; i++) {
if (Prev[i] == -1 && capacity[curr][i] > 0) {
s.push(i);
Prev[i] = curr;
}
}
}
// escape: no possible path
if (Prev[sink] == -1) break;
stack<int>
λ₯Ό μ΄μ©ν΄ DFSλ₯Ό ꡬννμΌλ©°, Prev[]
μ path historyλ₯Ό κΈ°λ‘νλ€. λ§μ½ sink
μ λλ¬νλ€λ©΄, κ·Έλν νμμ μ’
λ£νλ€. λ§μ½ sink
μ λλ¬νμ§ λͺ» νλ€λ©΄ μ¦ sinkλ‘ κ°λ κ²½λ‘λ₯Ό μ°Ύμ§ λͺ» νλ€λ©΄, Prev[sink]
μ κ°μ΄ κ°±μ λμ§ μμΌλ―λ‘ Prev[sink] == -1
μ΄ λλ€. μ΄ κ²½μ°λΌλ©΄, μκ³ λ¦¬μ¦μ μ’
λ£νλ€.
μ¬μ€ μμ μκ³ λ¦¬μ¦μ μλμ κ°μ΄ μ΅ΈνΌ κ°μ ν μ μλ€.
int Prev[MAX];
fill(Prev, Prev + MAX, -1);
Prev[source] = source;
stack<int> s;
s.push(source);
// dfs
while (!s.empty()) {
int curr = s.top();
s.pop();
for (int i = 0; i < MAX; i++) {
if (Prev[i] == -1 && capacity[curr][i] > 0) {
s.push(i);
Prev[i] = curr;
if (i == sink) break;
}
}
if (Prev[sink] != -1) break;
}
// escape: no possible path
if (Prev[sink] == -1) break;
λ€λ§ μ²μμ μ½λμ²λΌ ꡬνν΄λ ν΅κ³ΌνκΈ° λλ¬Έμ ν¬κ² μ κ²½μ°μ§λ λ§μ.
λ€μμ μ°Ύμ κ²½λ‘λ₯Ό μ΄μ©ν΄ κ·Έλνμ ν릴 μ λμ μ°ΎμμΌ νλ€. μ΄κ²μ μλμ μ½λλ‘ μνν μ μλ€.
// find possible max-flow
int flow = INT_MAX;
for (int v = sink; v != source; v = Prev[v]) {
flow = min(flow, capacity[Prev[v]][v]);
}
for (int v = sink; v != source; v = Prev[v])
ν¨ν΄μ κ·Έλν νμμμ κ²½λ‘λ₯Ό μ¬κ΅¬μ± ν λ μμ£Ό μ°λ ν
ν¬λμ΄λ―λ‘ μμ§ νλλ‘ νμ. π
λ€μμ κ²½λ‘μ μ λ flow
λ₯Ό νλ₯΄κ² νλ μμ
μ΄λ€. λ§μ°¬κ°μ§λ‘ κ²½λ‘λ₯Ό μ¬νμνλ©° μ λμ νλ €λ³΄λ΄λ©΄ λλ€.
// flow the max-flow
for (int v = sink; v != source; v = Prev[v]) {
capacity[Prev[v]][v] -= flow;
capacity[v][Prev[v]] += flow;
}
// update total flow!
total_flow += flow;
μ΄λ, μλ°©ν₯μΌλ‘λ capacityκ° λμ΄λλ€λ μ¬μ€μ μ μνμ.
μκ° λ³΅μ‘λ

μμ κ·Έλ¦Όμ <Ford-Fulkerson Algorithm>μμ μ΅μ μ μν©μ μμμ΄λ€. DFSλ‘ κ²½λ‘λ₯Ό μ°Ύλ 맀 μνλ§λ€ μ©λ 1μ κ°μ΄λ° κ°μ μ μ§λλ€κ³ νμ. κ·Έλ¬λ©΄ μ©λ 1,000μ μ±μ°κΈ° μν΄ 1,000μ iterationμ μνν΄μΌ νλ€. μ΄κ²μ DFSλ‘ κ²½λ‘λ₯Ό νμνλ <Ford-Fulkerson Algorithm>μ νκ³μ΄λ€ π₯
μμ μν©μ λ°νμΌλ‘ <Ford-Fulkerson Algorithm>μ μκ° λ³΅μ‘λλ₯Ό μ λν΄λ³΄μ. κ·Έλν $G_f$μμ μ΅λ μ©λμ΄ $f_{\max}$λΌκ³ νμ. νλ²μ DFS νμμΌλ‘ ν릴 μ μλ μ λμ μ΅μκ°μ 1μ΄λ―λ‘ μ΄ $f_{\max}$λ²μ DFSλ₯Ό μνν΄μΌ νλ€. μ΄λ, DFSμ μκ°λ³΅μ‘λκ° $O(V + E)$μ΄λ―λ‘, <Ford-Fulkerson Algorithm>μ $O((V + E) f_{\max})$ λ§νΌμ μκ°λ³΅μ‘λλ₯Ό κ°μ§λ€! λ§μ½ μ μ μ κ°―μ $V$κ° λ¬΄μν λ§νΌ μ λ€λ©΄ $O(E \cdot f_{\max})$λΌκ³ μ κΈ°λ νλ€.
Edmonds-Karp Algorithm
μμ <Ford-Fulkerson Algorithm>μ μ½λμμλ DFSλ₯Ό ν΅ν΄ λ¬Έμ λ₯Ό ν΄κ²°νλ€. μ΄λ, κ°μ μ μ°Ύλ κ³Όμ μ BFSλ‘ μννλ€λ©΄, <Edmonds-Karp Algorithm>μ΄ λλ€!
<Edmonds-Karp Algorithm>μ κΈ°μ‘΄ <Ford-Fulkerson Algorithm>μ΄ μ΅λ μ©λ $f_{\max}$κ° ν° κ²½μ°μ μ λμνμ§ λͺ»νλ€λ μ λλ¬Έμ μ μλ μκ³ λ¦¬μ¦μ΄λ€. κ·Έλ°λ° DFSμμ BFSλ‘ λ°κΎΈλ©΄ 무μμ΄ λ¬λΌμ§λ κ±ΈκΉ?
λ€μ μμ μμ λ₯Ό ν΅ν΄ μ΄ν΄λ³΄μ.

μΌλ¨ 맨μ²μμλ A - B - C - D
μ κ²½λ‘λ‘ μ λμ΄ νλ λ€κ³ νμ. κ·Έ λ€μμ νλ₯Ό μ λμ μ΄ν΄λ³΄λ©΄,
- λ°©λ¬Έ: [A], ν: [B, C]
- λ°©λ¬Έ: [A, B], ν: [D] (B -> Cλ μ΄λ―Έ μ©λμ΄ λ€ μ°ΌκΈ° λλ¬Έμ λλ¬ν μ μλ€)
- λ°©λ¬Έ: [A, B, D], ν: []
- 999λ§νΌμ μ λμ νλ €λ³΄λΈλ€.
μ΄ κ³Όμ μ λ°λ³΅νλ©΄ κΈ°μ‘΄μ <Ford-Fulkerson Algorithm> λ³΄λ€ ν¨μ¬ μ μ iterationμΌλ‘ μ΄μ λμ ꡬν μ μλ€.
<Edmonds-Karp Algorithm>μ flowμ κ°λ³΄λ€λ edge $E$μ λ μν₯μ λ°κ² λλ€. μμΈν μ¦λͺ
μ ꡬμ¬κ³Όλμ λΈλ‘κ·Έλ₯Ό ν΅ν΄ μ΄ν΄λ³΄μ π λμ€μ μ 리νκ² μ΅λλ€β¦
κ²°λ‘ μ <Edmonds-Karp Algorithm>μ΄ $O(VE^2)$μ μκ°λ³΅μ‘λλ₯Ό κ°μ§λ€!!
μ΄κ²μΌλ‘ λ€νΈμν¬ νλ‘μ° λ¬Έμ μ κΈ°λ³Έμ μΈ λ μκ³ λ¦¬μ¦μΈ <Ford-Fulkerson Algorithm>κ³Ό <Edmonds-Karp Algorithm>μ μ΄ν΄λ³΄μλ€. λ μκ³ λ¦¬μ¦μ μκ°λ³΅μ‘λκ° λ€λ₯΄κΈ° λλ¬Έμ μν©μ λ§κ² μ μ νκ² μ νν΄ μ¬μ©νλ©΄ λλ€.
λ€μ ν¬μ€νΈλ‘λ λ€νΈμν¬ νλ‘μ°λ₯Ό μ΄μ©ν΄ ν΄κ²°ν μ μλ λ¬Έμ λ€μ λν΄ λ€λ£¬λ€. λνμ μΈ λ¬Έμ λ‘ <Bipartite Matching; μ΄λΆ 맀μΉ>κ³Ό λ€νΈμν¬ νλ‘μ°μ μ μ½(constraint)λ₯Ό μΆκ°ν λ²μ μ λ¬Έμ λ€μ μ΄ν΄λ³Ό μμ μ΄λ€ π
π Bipartite Matching