Dinicのアルゴリズム

ディニッツと呼ぶ。ディニックではないらしい。

グラフ$ G:=(V,E,c)に対して、最大流問題を解いて最大フロー$ fを求めるアルゴリズム

$ \mathrm{O}(|E||V|^2)？

事前定義

$ f:フロー(変数)

$ A: $ fに対し更新したフロー$ A(f)を返す、Dinicのアルゴリズムを表す関数

$ Aを一回$ fに適用することで、アルゴリズムが一回反復されたことを意味する。

$ f_i:フロー$ Aを$ i回適用したときのフロー変数のキャプチャ

$ G_f := (V, E_f, c_f): 残余ネットワーク

$ s, t \in V: 始点と終点

要するに

グラフ$ Gに対してフロー増加可能パスを発見する

ただし、流せる全ての辺の中で辺数最短経路だけを列挙する。

(残余ネットワーク; Def.2レベルグラフ (1))

そして、それらのパスを一度に詰まらせるフローを作る

ブロックフロー

そのフローを足し合わせることで更新して繰り返す

改良点

Ford-Fulkerson法では、一回のパスに沿ったフロー増加ごとに辺数最短路を探索しなくてはならなかった。

このアルゴリズムでは一回最短路を求めただけで一気に複数のフロー増加可能パスを詰まらせられるようになった。

Def.1 レベル

残余ネットワーク$ G_fの各頂点に対して定義される関数$ \mathrm{level}もしくはその実数値$ \mathrm{level}(v)

頂点$ v \in Vに対し、$ \mathrm{level}(v)は

$ sからの$ tまでの辺数最短路の長さである。

$ sから$ tが到達不可能な場合は$ +\infinとする。

残余ネットワーク$ G_f上の辺数最短路であることに注意

Def.2 レベルグラフ

$ G_fの部分グラフ$ L_f := (V_{Lf} \sub V, E_{Lf} \sub E, c_f)で、以下を全て満たすもの。

(1) $ v \in V_{Lf} \Leftrightarrow \mathrm{level}(v) < + \infin

$ V_{Lf}は$ sから到達可能な頂点全体の集合。

(2) $ (v, w) \in E_{Lf} \Leftrightarrow \mathrm{level}(w) = \mathrm{level}(v) + 1

$ vの最短路を一つ伸ばして$ wに到達できる場合にだけ辺を引く。

Thm.2-1 レベルグラフはDAGである。

仮に閉路$ rがあったと仮定する。閉路$ rの辺数を$ lとしよう。

このとき、閉路$ r中の辺を一つ経るたびに辺のレベルは1増大する。

つまり、$ rを巡回すれば、レベルは$ l増加する。

ゆえに、閉路中の点$ w \in rをとれば、

点$ wに対して、

$ \mathrm{level}(w)

$ \mathrm{level}(w) + l

$ \mathrm{level}(w) + 2l

$ \vdots

という複数のレベルを評価することができる。しかし、これはレベルが関数であることと矛盾している。

以上より、レベルグラフには閉路が存在せず、DAGである。

/icons/notepad.icon付記

この性質から、レベル順に$ L_fの頂点をソートするとトポロジカルソートを行ったことになる。

Thm.2-2 レベルグラフの辺の本数

Def.3 ブロックフロー

$ L_fに対して定義されるフロー$ f'

始点$ sから終点$ tまでの任意のパス$ pに対して、$ f'(e) = c_{f}(e)のように飽和している辺$ eが$ p中に存在している

Thm.3-1 ブロックフローの創成にかかる時間計算量

Lem.4-1 フロー増加可能パスの伸張

Lem.4-2 反復回数の上界

Thm.5 アルゴリズムの時間計算量

参考文献

コンピュータサイエンス教科書シリーズ19 数理計画法/加藤直樹