最大流を求めるアルゴリズム
最大流、まとめました
残余グラフ
残余グラフ (residual graph) は最大流を求める過程をいい感じに表すためのグラフ
残余グラフの辺は、その辺のフローをどれだけ変化させられるかを表す
たとえば、こういうネットワークを考える
辺には$ \text{流量 / 容量}が書いてある
https://scrapbox.io/files/66b714dcc4beae001cf4ccf1.png
↑を残余グラフで表すと、こうなる
https://scrapbox.io/files/66b714d99bc139001d005aaf.png
各辺の値は元のネットワークの容量になっている
辺のフローは容量分増やすことができるから
残余グラフにフローを流すには、辺の重みを減らし、逆向きの辺の重みを増やす
たとえば、上のグラフにこのようにフローを流した状態を考える
https://scrapbox.io/files/66b714d6c2f359001c22a5ce.png
↑を残余グラフで表すと、こうなる
https://gyazo.com/7c94a0f27830257bd5f2d7b6edd41df9
もともと重み$ 6だった辺に注目してみると、重み$ 4の辺と、重み$ 2の逆向きの辺になっている
この辺は容量$ 6で、$ 2のフローが流れているので、$ 4の余裕があり、逆に$ 2減らすこともできる
このように、残余グラフの辺は「あとどれだけフローを減らせるか」も同時に表すことができる
増加路ベースのアルゴリズム
増加路は、それに沿ってフローを流すと全体のフローが増えるような$ s-tパスのこと
増加路ベースのアルゴリズムは増加路に沿ってひたすらフローを流す
Ford-Fulkerson
Ford-Fulkersonは、フローを流せなくなるまで流す、ということを繰り返す貪欲なアルゴリズム
残余グラフ上に$ sから$ tのパス（増加路）があれば、そこにパス上の重みの最小値分のフローを流す
このとき、増加路を見つけるにはDFSを使う
計算量
計算量は$ Eを辺数、$ fを最大フローとして、$ O(Ef)
毎回の繰返しでパスを探すのに$ O(E)かかり、繰返す度にフローは少なくとも$ 1増えるので繰返しは最大で$ f回
Edmonds-Karp
Edmonds-KarpはFord-Fulkersonの改良版アルゴリズムで、フローを流すパスの選び方を工夫したもの
増加路を見つけるときにDFSの代わりにBFSを使うことで、常に辺数が最小の増加路を選ぶことになる
実装はFord-Fulkersonとほとんど変わらない（BFSなので再帰での実装は困難、キューで実装する）
計算量
$ Eを辺数、$ Vを頂点数、$ fを最大フローとして、$ O(\min\{Ef, VE^2\})
辺数が最小の増加路にフローを流すとき、別の増加路ができるとしても、その辺数は今より少なくはならない
増加路の長さはどんどん伸びていくが、$ V頂点のパスグラフの長さは$ O(V)なので最大でも$ O(V)
また、$ 1回の繰返しについて、かならず$ 1本の辺が飽和するため、$ O(E)でもある
ブロッキングフローベースのアルゴリズム
「流せるだけ流す」をすべてのパスに同時にやる感じ
Dinic
DinicはEdmonds-Karpの変形のような感じ
このアルゴリズムは
dual step: 辺数が最小な全ての増加路をBFSで列挙する（レベルグラフを作る）
primal step: レベルグラフにDFSで流せるだけのフロー（ブロッキングフロー）を流す
を繰り返す
計算量
$ Eを辺数、$ Vを頂点数、$ fを最大フローとして、$ O(\min\{Ef, V^2E\})
また、特殊なグラフの場合は計算量がさらに小さくなる場合もある（二部マッチングに使われるグラフでは$ O(E \sqrt V)など）
$ O(Ef): Ford-Fulkersonと同じく
$ O(V^2E):
1回の繰返しで、最短の増加路の辺は1以上増える→繰返しはO(V)回
dual stepはBFSなのでO(E)
primal stepはレベルグラフ（DAG）のフローなのでO(VE)
参考
容量スケーリング法
一度に流せるフローが大きな増加路から順に選びたい
使う辺の容量に下限をつけ、最初は下限を大きく、使える辺がなくなったらその半分の下限、というふうにして増加路を選ぶ
実装はほとんどスケーリング部分を追加するだけ
計算量
$ Eを辺数、$ Vを頂点数、$ Uを辺容量の最大値として
Ford-Fulkerson + 容量スケーリング: $ O(E^2 \log U)
Dinic + 容量スケーリング: $ O(VE \log U)
参考
プリフローベースのアルゴリズム
プリフローベースのアルゴリズムでは、増加路ベースやブロッキングフローベースのアルゴリズムとは違い、頂点に入るフロー＞頂点から出るフローとなることを許す
増加路ベースのアルゴリズムはフローを増やしていく感じだとすると、プリフローは、まずフローをたくさん流して、そこから過剰がなくなるように減らしていく感じ
Goldberg-Tarjan
Goldberg-TarjanはPush/Relabelとも呼ばれる
これはPush操作とRelabel操作を指している
このアルゴリズムでは、すべての頂点$ vは距離ラベル$ 0 \le h_v \le Vと剰余フロー$ x_v \ge 0を持つ
距離ラベルは整数で、剰余フローは頂点に入るフローから頂点を出るフローを引いた量
剰余フローが$ 0でない頂点をアクティブな頂点と呼ぶ
はじめ、シンク$ tのラベルは$ Vで、それ以外の頂点のラベルは$ 0
また、ソース$ sの剰余は$ \inftyで、それ以外の頂点の剰余は$ 0
push操作かrelabel操作のどちらかをできる限り繰り返す
push操作
アクティブ（$ x_u > 0）な頂点$ uから伸びる辺$ e(u \to v)で、$ h_u = h_v + 1となっているものがあるなら、$ eの容量一杯のフローを流す
$ x_\Delta = \min(x_u, \text{cap}_e)とすると、
$ x_u \leftarrow x_u - x_\Delta
$ x_v \leftarrow x_v + x_\Delta
relabel操作
アクティブな頂点$ uに対してpush操作ができないとき、頂点$ uのラベルを貼り替える
辺$ u \to vがあるとき、$ h_u > h_vとなるようにする
つまり、$ h_u = 1 + \max_{u \to v} h_v
TODO:実行例
ヒューリスティック
Goldberg-Tarjanは最悪計算量はDinicと同じだが、そのままだと平均的に遅い（多くの場合Dinicの方がかなり高速）
ただし、ヒューリスティックを入れることでかなり高速化できる
以下はヒューリスティックの例
Highest Selection $ O(V^2\sqrt E): バケットソートのようにして、距離ラベルが大きい頂点から順に処理する
FIFO $ O(V^3): アクティブな頂点の管理にキューを使って、アクティブになった順番で処理をする
Global Relabeling $ O(V^2E): $ O(V)回操作するごとに$ l_v \leftarrow \text{dist}(s, v)をする
Gap Relabeling $ O(V^2E): ギャップがあった場合上側を全消去する
計算量
$ O(V^2E): そのまま
$ O(V^3): FIFO or Relabel to Front
$ O(V^2\sqrt E): Highest Selection
参考