ディニッツ法

ディニッツは1969年1月ゲオルギー・アデルソン・ヴェルスキー（英語版）の修士課程の生徒としてディニッツ法を編み出した。数十年後、当時のことを以下のように語った^[2]:

アデルソン・ヴェルスキーのアルゴリズムの講義では毎回次週の講義内容に関する問題の課題を出していた。ディニッツ法はこの課題の回答として出来上がったものである。当時（ディニッツ自身は）既に解法として知られていたフォード・ファルカーソン法について知らなかった…。

⋮

無知なことは時に役立つことがある。もし（フォード・ファルカーソン法での）飽和した辺に対する手続きを既に知っていたとしたら、ディニッツ法は生み出されていないだろう。

1970年にディニッツは Doklady Akademii Nauk SSSR に論文を寄稿した。1974年には（ディニッツの博士課程指導学生の）サイモン・イーブン（英語版）およびテクニオン・イスラエル工科大学のアーロン・イタイはディニッツ法やアレキサンダー・カルザノフ（英語版）が考案したブロッキングフローに関する概念に強く興味を抱いた。しかしながら、これらの論文は掲載誌の Doklady Akademii Nauk SSSR に規定されているページ数の制限（4頁）により、論文の内容を理解するのに難儀した。論文の解読を続けたことで、結果として層別ネットワークに対する手続きを除いた論文の内容を三日間で理解することができた。両者は著者の名前を間違えながらも、数年かけてディニッツ法に関する講義を行って世間に知らしめていった。イーブンとイタイは層別ネットワークの代わりに幅優先探索と深さ優先探索を組み合わせたディニッツ法を普及したため、現在ではこの方法によるディニッツ法が一般的に知られている^[2]。

フォード・ファルカーソン法が提案されてから約10年間は無理数の辺容量を持つような一般のネットワークに対する強多項式時間アルゴリズムの存在性は示されていなかった。そのため最大流問題が強多項式時間で解けるかは不明であった。ディニッツ法と（1972年発表の）エドモンズ・カープ法はフォードファルカーソン法において各反復で求まる増加路が最短路であるならば、増加路の長さが単調増加するため、有限の反復回数で必ず終了することをそれぞれ独立して証明した。

ネットワーク ${\displaystyle G=((V,E),c,f,s,t)}$において辺容量を ${\displaystyle c(u,v)}$、フローを ${\displaystyle f(u,v)}$ とする。このとき、

残余容量 ${\displaystyle c_{f}\colon V\times V\to R^{+}}$ は以下のように定義される:

1. もし、${\displaystyle (u,v)\in E}$ ならば、

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

2. もし、${\displaystyle (v,u)\in E}$ ならば、

   ${\displaystyle c_{f}(u,v)=f(v,u)}$

3. そうでなければ、${\displaystyle c_{f}(u,v)=0}$

残余ネットワークは重みなしのネットワーク ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$ と定義される。ただし、

${\displaystyle E_{f}=\{(u,v)\in V\times V\colon \;c_{f}(u,v)>0\}}$.

増加路は残余ネットワーク ${\displaystyle G_{f}}$ における路 ${\displaystyle s}$–${\displaystyle t}$ である。

${\displaystyle \operatorname {dist} (v)}$ は ${\displaystyle G_{f}}$ において始点 ${\displaystyle s}$ から頂点 ${\displaystyle v}$ への最短路の値を表す。このとき ${\displaystyle G_{f}}$ におけるレベルグラフは ${\displaystyle G_{L}=((V,E_{L}),c_{f}|_{E_{L}},s,t)}$ と定義される。ただし、

${\displaystyle E_{L}=\{(u,v)\in E_{f}\colon \;\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$

である。

ブロッキングフローは ${\displaystyle s}$ から ${\displaystyle t}$ へのフロー ${\displaystyle f'}$ を表し、${\displaystyle G'=((V,E_{L}'),s,t)}$ で定義される。ただし、${\displaystyle E_{L}'=\{(u,v)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ であり、${\displaystyle s}$ から ${\displaystyle t}$ への路は含まれない^{[注釈 2][3]}。

ディニッツ法

入力: ネットワーク ${\displaystyle G=((V,E),c,s,t)}$

出力: ${\displaystyle s}$ から ${\displaystyle t}$ へのフロー ${\displaystyle f}$ の最大値

1. 各辺 ${\displaystyle e\in E}$ のフローを ${\displaystyle f(e)=0}$ とおく。
2. ${\displaystyle G}$ における ${\displaystyle G_{f}}$ から ${\displaystyle G_{L}}$ を構築する。もし、${\displaystyle \operatorname {dist} (t)=\infty }$ が存在するならば、アルゴリズムは停止し、${\displaystyle f}$ を出力する。
3. ${\displaystyle G_{L}}$ におけるブロッキングフロー ${\displaystyle f'}$ を求める。
4. ${\displaystyle f'}$ から増加路 ${\displaystyle f}$ を求め、ステップ2へ戻る。

反復ごとにブロッキングフローの層の数は少なくとも1ずつ増えることから、ブロッキングフローは最大でも ${\displaystyle |V|-1}$ の層の数となる。また以下のことが言える:

• レベルグラフ ${\displaystyle G_{L}}$ は幅優先探索によって計算量 ${\displaystyle O(E)}$ で求まる。
• レベルグラフ ${\displaystyle G_{L}}$ におけるブロッキングフローは計算量 ${\displaystyle O(VE)}$ で求まる^{[注釈 3]}。

このことから一回の反復にかかる計算量は ${\displaystyle O(E+VE)=O(VE)}$ となる。結果として、全体の計算量は ${\displaystyle O(V^{2}E)}$ となる^[2]。

動的木（英語版）と呼ばれるデータ構造を用いると、各反復におけるブロッキングフローは計算量 ${\displaystyle O(E\log V)}$ まで減少させることができるため、ディニッツ法の計算量は ${\displaystyle O(VE\log V)}$ まで改良することができる。

ディニッツ法を以下で説明する。レベルグラフ ${\displaystyle G_{L}}$ において頂点の赤色の数値は ${\displaystyle \operatorname {dist} (v)}$ を表す。また青色の辺からブロッキングフローが求まる。

さらに見る , ...

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	ブロッキングフローは以下の路から構成される: フロー4を持つ路: ${\displaystyle \{s,1,3,t\}}$ フロー6を持つ路: ${\displaystyle \{s,1,4,t\}}$ フロー4を持つ路: ${\displaystyle \{s,2,4,t\}}$ それゆえ、ブロッキングフローは 14 となり、フロー ${\displaystyle |f|}$ は ${\displaystyle 14}$ となる。増加路は3つの辺から構成されることに注意する。
2.
	ブロッキングフローは以下の路から構成される: フロー5を持つ路: ${\displaystyle \{s,2,4,3,t\}}$ それゆえ、ブロッキングフローは 5 となり、フロー ${\displaystyle |f|}$ は ${\displaystyle 14+5=19}$ となる。増加路は4つの辺から構成されることに注意する。
3.
	${\displaystyle G_{f}}$ において ${\displaystyle t}$ に到達することはできないことから、アルゴリズムは終了してフローの最大値19を返す。各反復ごとに増加路となる辺の数は一つ前の反復より少なくとも一つ増加することに注意する。

閉じる