Ford-Fulkerson法とは
グラフの最大流を求める問題を解くアルゴリズムです。やっていることはdfsの繰り返しですが、「逆辺」を考慮に入れなければなりません。最大流とは、
- グラフ$G=(e,v)$において、$s$から$t$に向かって最大でどれだけの量のフローを流せるかを求める
という問題のことです。今回の記事では詳しい説明を省略します。
Ford-Fulkerson法は以下の手順で行います。
- $G$に、$e$の逆辺を追加する。(逆辺を$e^{-1}$で表します)
- $f(e)<=c(e)$を満たす辺と、$f(e^{-1})>0$を満たす逆辺のみで構成されるグラフ(このようなグラフを残余グラフと呼びます)で、$s$から$t$に向かってdfsをし、パスを見つける。答えにパスの流量を加算する。
- そのようなパスが存在しなくなるまで、2を繰り返す。
逆辺とは、$e=${$a,b$}に対しての$e^{-1}=${$b,a$}のことです。$e$が$f$のフローを持っている状態のとき、逆辺は$f$の容量を持っているとします。逆辺の容量は「$e$においてどれだけフローを押し戻せるか」をあらわしていると理解すると分かりやすいと思います。
この手順で最大流が求まる証明は、蟻本を読むか、賢い人がブログで解説しているのでそちらを参照してください。
実装例
初期変数として
struct edge { int to, cap, rev; }; //辺の構造体 to:行き先, cap:容量, rev, 逆辺の位置
vector<edge> G[MAX_V]; //辺の隣接リスト表現
bool used[MAX_V]; //dfsで調べたか
を定義しておきます。辺を追加する操作を以下のように実装します。
void add_edge(int _from, int _to, int cap){
edge e = { _to, cap, G[_to].size() }; G[_from].push_back(e);
e = { _from, 0, (int)G[_from].size() - 1 }; G[_to].push_back(e);
}
逆辺の位置をvectorの現在の最後尾で管理しています。これにより$e$の逆辺には
G[e.to][e.rev]
でアクセスすることができます。
dfsで$s$から$t$へのパスを求める操作を以下のように実装します。ある$e$において、元の容量から流量を引くことで、残りの容量を管理します。こうすることで、残余グラフにおける辺と逆辺を1つの条件で発見することができます。
int dfs(int v, int t, int f) {//sからtへ移動可能ならそのルートの最大流量を返し、不可能なら0を返す。
if (v == t) return f; //到達した
used[v] = true; //調べ終わった
for (int i = 0; i < G[v].size(); i++) {
edge& e = G[v][i];
if (!used[e.to] && e.cap > 0) { //残余グラフの辺のみ
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d; //残り容量はd減少
G[e.to][e.rev].cap += d; //逆辺の容量はdだけ増加する
return d;
}
}
}
return 0; //到達できない
}
このdfsで、$s$から$t$へのパスが1つ見つかるか、パスが存在しないことが分かります。
これをパスが存在しなくなるまで、以下のように繰り返します。
int max_flow(int s, int t) {//最大流を求める
int flow = 0;
while (true) {
memset(used, 0, sizeof(used));
int f = dfs(s, t, infi);
if (f == 0) return flow;
flow += f;
}
}
計算量
dfsでフローが1のパスしか見つからないことが永遠に繰り返されると、dfsの繰り返し回数は最大で$F$回です($F$:考えうる流量の最大値)。dfsは$G$が一直線の有向グラフの場合$|E|$かかります。
従って、Ford-Fulkerson法の計算量は$O(F|E|)$となるのですが、よく考えると
- dfsでフローが1のパスしか見つからないことが永遠に繰り返される
- $G$が一直線の有向グラフ
というのは両立しないので、実はここまでの計算量はかからず、$O(F|E|)$で危なそうな程度なら通ることが多いようです。
補足 : 色々な問題ケース
上の実装は最もシンプルなケースを考えたもので、
- 頂点に容量はなく、入ってくる流量と出ていく流量は等しい
- グラフは有向グラフ
- 流れの元となる点$s$(ソース)と流れの終点$t$(シンク)はそれぞれ1つ
- 辺に対する最小流量は全て$0$
という条件で考えました。これらの条件が満たされないグラフに対して、少し工夫することで今回紹介した実装をそのまま使うことができます。
1. 頂点に容量がある場合
頂点で容量があるということは、その頂点内に辺が存在してそこに容量上限まではフローが流れるということです。
頂点$v$の容量を$c$とすると、頂点$v$を容量$0$の頂点$v_{in}$と$v_{out}$に分けて、$v_{in}$と$v_{out}$をつなぐ容量$c$の辺を追加すれば、同じ状態にできます。もともと$v$に入ってきていた辺は$v_{in}$につなぎ、$v$から出ていた辺は$v_{out}$からつなげばよいです。
2. 無向グラフの場合
無向グラフは双方向の有向グラフと考えることができるので、無向辺$e$=($a,b$)を、2つの有向辺$e_1$={$a,b$}と$e_2$={$b,a$}に分けて追加すればよいです。一見辺の合計容量が倍になってしまうように感じますが、向きが逆なため、最大でも$c$しか流れないことが分かります。
3. 複数のソース・シンクがある場合
例えば複数のソース$s_1,s_2,s_3...$があり、それぞれの最大流出量が決まっているなら、新たに別の点$s$を作成して、$s$からすべてのソースに対してそれぞれの最大流出量分の容量を持つ辺を追加することで、$s$をただ1つのソースとして問題を解くことができます。シンクに関しても同様です。
4. 辺に最小流量の条件がある場合
辺$e$が容量$c(e)$および最小流量$b(e)$によって、$b(e)≦f(e)≦c(e)$で条件付けられていた場合を考えます。この不等式は$f^{'}(e)=f(e)-b(e)$とすることで、$0≦f^{'}(e)≦c(e)-b(e)$となり、最小流量の制限がないケースに帰着できます。