ディニッツ法のソースを表示

'''ディニッツ法'''（ディニッツほう、{{Lang-en-short|Dinic's algorithm, Dinitz's algorithm}}）とは、1970年にイスラエル（元はソ連）のコンピュータ科学者の{{仮リンク|イェフィム・ディニッツ|en|Yefim Dinitz}}により提案された[[ネットワークフロー]]における[[最大流問題]]に対する{{仮リンク|強多項式時間|en|strongly polynomial}}アルゴリズムである<ref>{{cite journal | author = E. A. Dinic |author-link = :en:Yefim Dinitz |title = Algorithm for solution of a problem of maximum flow in a network with power estimation | journal = Doklady Akademii Nauk SSSR | volume = 11 | year = 1970 | pages = 1277&ndash;1280 | url=http://www.cs.bgu.ac.il/~dinitz/D70.pdf}}</ref>。ディニッツ法は計算量 <math>O(|V|^2|E|)</math> で動作し、同じく最短増加路を求め計算量 <math>O(|V||E|^2)</math> で動作する[[エドモンズ・カープ法]]に類似している。ディニッツ法はレベルグラフとブロッキングフロー{{Efn|{{Lang-en-short|level graph, blocking flow}}}}という概念を導入することで上記の計算量を達成している。

== 歴史 ==
ディニッツは1969年1月{{仮リンク|ゲオルギー・アデルソン・ヴェルスキー|en|Georgy Adelson-Velsky}}の修士課程の生徒としてディニッツ法を編み出した。数十年後、当時のことを以下のように語った<ref name="even's version" />:
{{blockquote
| text=アデルソン・ヴェルスキーのアルゴリズムの講義では毎回次週の講義内容に関する問題の課題を出していた。ディニッツ法はこの課題の回答として出来上がったものである。当時（ディニッツ自身は）既に解法として知られていた[[フォード・ファルカーソン法]]について知らなかった…。
⋮
無知なことは時に役立つことがある。もし（フォード・ファルカーソン法での）飽和した辺に対する手続きを既に知っていたとしたら、ディニッツ法は生み出されていないだろう。
| multiline=yes
}}

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

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

== 定義 ==
ネットワーク <math>G = ((V,E),c,f,s,t)</math>において辺容量を <math>c(u,v)</math>、フローを <math>f(u,v)</math> とする。このとき、

: '''残余容量''' <math>c_f\colon V\times V \to R^+</math> は以下のように定義される:
:# もし、<math>(u,v)\in E</math> ならば、
:#: <math>c_f(u,v) = c(u,v) - f(u,v) </math>
:# もし、<math>(v,u)\in E</math> ならば、
:#: <math>c_f(u,v) = f(v,u) </math>
:# そうでなければ、<math>c_f(u,v) = 0</math>

:'''残余ネットワーク'''は重みなしのネットワーク <math>G_f = ((V, E_f), c_f|_{E_f}, s, t)</math> と定義される。ただし、
:: <math>E_f = \{(u,v)\in V \times V \colon\; c_f(u,v) > 0\}</math>.

:'''増加路'''は残余ネットワーク <math>G_f</math> における路 <math>s</math>–<math>t</math> である。

:<math>\operatorname{dist}(v)</math> は <math>G_f</math> において始点 <math>s</math> から頂点 <math>v</math> への最短路の値を表す。このとき <math>G_f</math> における'''レベルグラフ'''は <math>G_L = ((V, E_L), c_f|_{E_L}, s,t)</math> と定義される。ただし、
:: <math>E_L = \{(u,v)\in E_f \colon\; \operatorname{dist}(v) = \operatorname{dist}(u) + 1\}</math>
である。

:'''ブロッキングフロー'''は <math>s</math> から <math>t</math> へのフロー <math>f'</math> を表し、<math>G' = ((V,E_L'), s, t)</math> で定義される。ただし、<math>E_L' = \{(u,v) \colon\; f'(u,v) < c_f|_{E_L}(u,v)\}</math> であり、<math>s</math> から <math>t</math> への路は含まれない{{Efn|このことは <math>E_L' = \{(u,v) \colon\; f'(u,v) < c_f|_{E_L}(u,v)\}</math> を満たす飽和した辺が取り除かれた部分グラフにおいては <math>s</math> から <math>t</math> への路は存在しないことを意味する。言い換えると、ブロッキングフローには <math>s</math> から <math>t</math> への路の中に少なくとも一つ飽和した辺が含まれている。}}{{sfn|Tarjan|1983|p=102}}。

== アルゴリズム ==
'''ディニッツ法'''
: ''入力'': ネットワーク <math>G = ((V, E), c, s, t)</math>
: ''出力'': <math>s</math> から <math>t</math> へのフロー <math>f</math> の最大値
# 各辺 <math>e\in E</math> のフローを <math>f(e) = 0</math> とおく。
# <math>G</math> における <math>G_f</math> から <math>G_L</math> を構築する。もし、<math>\operatorname{dist}(t) = \infty</math> が存在するならば、アルゴリズムは停止し、<math>f</math> を出力する。
# <math>G_L</math> におけるブロッキングフロー <math>f'</math> を求める。
# <math>f'</math> から増加路 <math>f</math> を求め、ステップ2へ戻る。

== 分析 ==
反復ごとにブロッキングフローの層の数は少なくとも1ずつ増えることから、ブロッキングフローは最大でも <math>|V|-1</math> の層の数となる。また以下のことが言える:

* レベルグラフ <math>G_L</math> は[[幅優先探索]]によって計算量 <math>O(E)</math> で求まる。
* レベルグラフ <math>G_L</math> におけるブロッキングフローは計算量 <math>O(VE)</math> で求まる{{Efn|ブロッキングフローは Advance および Retreat 操作により計算量 <math>O(E)</math> で求めることができる<ref>{{Cite web |url=http://courses.csail.mit.edu/6.854/06/scribe/scribe11.pdf|title=Blocking flow |author=Salman Abolfathe, Jaime Quinonez |archive-url=https://web.archive.org/web/20240522170614/https://courses.csail.mit.edu/6.854/06/scribe/scribe11.pdf |archive-date=2024-05-22 |work=4 Advanced Algorithm |year=2006 |accessdate=2025-03-03 |url-status=dead }}</ref>。}}。

このことから一回の反復にかかる計算量は <math>O(E + VE) = O(VE)</math> となる。結果として、全体の計算量は <math>O(V^2 E)</math> となる<ref name="even's version">{{cite book | first=Yefim | last=Dinitz | author-link=:en:Yefim Dinitz | editor1=Oded Goldreich | editor-link1=:en:Oded Goldreich | editor2=Arnold L. Rosenberg | editor-link2=:en:Arnold L. Rosenberg | editor3=Alan L. Selman | editor-link3=:en:Alan Selman | title=Theoretical Computer Science: Essays in Memory of [[:en:Shimon Even|Shimon Even]] | chapter=Dinitz' Algorithm: The Original Version and Even's Version | series=Lecture Notes in Computer Science | year=2006 | volume=3895 | publisher=Springer | isbn=978-3-540-32880-3 | pages=218–240 | doi=10.1007/11685654_10 | chapter-url=https://link.springer.com/chapter/10.1007/11685654_10}}</ref>。

{{仮リンク|動的木|en|dynamic trees}}と呼ばれるデータ構造を用いると、各反復におけるブロッキングフローは計算量 <math>O(E \log V)</math> まで減少させることができるため、ディニッツ法の計算量は <math>O(VE \log V)</math> まで改良することができる。

=== 特別なケース ===
単位容量を持つネットワークにおいては強多項式時間が保たれる。ブロッキングフローは計算量 <math>O(E)</math> で求めることができ、反復も <math>O(\sqrt{E})</math> もしくは <math>O(V^{2/3})</math> を超えない範囲で終了することが保証されている{{Efn|計算量 <math>O(V^{2/3})</math> は、2頂点において同じ向きの多重辺が含まれていないときに成り立ち、計算量 <math>O(\sqrt E)</math> についてはこのような仮定無しに保証される。}}。すなわちディニッツ法は計算量 <math>O(\min\{V^{2/3}, E^{1/2}\}E)</math> で動作する<ref name="Even1975">{{cite journal|last1=Even|first1=Shimon|last2=Tarjan|first2=R. Endre|year=1975|title=Network Flow and Testing Graph Connectivity|journal=SIAM Journal on Computing|volume=4|issue=4|pages=507–518|issn=0097-5397|doi=10.1137/0204043}}</ref>。

最大[[二部グラフ|二部マッチング]]問題に対するネットワークにおいては、反復の上界が <math>O(\sqrt{V})</math> となることが知られており、計算量は <math>O(\sqrt{V} E)</math> で動作する。このことは{{仮リンク|ホップクロフト・カープ法|en|Hopcroft–Karp algorithm}}として知られている。一般的に言えば、ネットワークにおいてシンクおよびソースを除く各頂点を結ぶ辺がすべて容量1の入る辺もしくは容量1の出る辺であり、他の辺の容量がすべて整数値をとる単位ネットワーク上で成り立つ{{sfn|Tarjan|1983|p=102}}。

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

{| class="wikitable" style="text-align:center; width:915px;" border="1"
|-
! width="15px" |

! <math>G</math>
! <math>G_f</math>
! <math>G_L</math>
|-
! 1.
| [[File:Dinic algorithm G1.svg|300px]]
| [[File:Dinic algorithm Gf1.svg|300px]]
| [[File:Dinic algorithm GL1.svg|300px]]
|-
| 
| align="left" colspan="3" |
ブロッキングフローは以下の路から構成される:
# フロー4を持つ路: <math>\{s, 1, 3, t\}</math>
# フロー6を持つ路: <math>\{s, 1, 4, t\}</math>
# フロー4を持つ路: <math>\{s, 2, 4, t\}</math>
それゆえ、ブロッキングフローは 14 となり、フロー <math>|f|</math> は <math>14</math> となる。増加路は3つの辺から構成されることに注意する。
|-
! 2.
| [[File:Dinic algorithm G2.svg|300px]]
| [[File:Dinic algorithm Gf2.svg|300px]]
| [[File:Dinic algorithm GL2.svg|300px]]
|-
| 
| align="left" colspan="3" |
ブロッキングフローは以下の路から構成される:
# フロー5を持つ路: <math>\{s, 2, 4, 3, t\}</math>
それゆえ、ブロッキングフローは 5 となり、フロー <math>|f|</math> は <math>14 + 5 = 19</math> となる。増加路は4つの辺から構成されることに注意する。
|-
! 3.
| [[File:Dinic algorithm G3.svg|300px]]
| [[File:Dinic algorithm Gf3.svg|300px]]
| [[File:Dinic algorithm GL3.svg|300px]]
|-
| 
| align="left" colspan="3" |
<math>G_f</math> において <math>t</math> に到達することはできないことから、アルゴリズムは終了してフローの最大値19を返す。各反復ごとに増加路となる辺の数は一つ前の反復より少なくとも一つ増加することに注意する。
|-
|}

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
* {{cite book |first=Yefim |last=Dinitz |author-link=:en:Yefim Dinitz |editor1=Oded Goldreich |editor-link1=:en:Oded Goldreich |editor2=Arnold L. Rosenberg |editor-link2=:en:Arnold L. Rosenberg |editor3=Alan L. Selman |editor-link3=:en:Alan Selman |title=Theoretical Computer Science: Essays in Memory of [[:en:Shimon Even|Shimon Even]] |chapter=Dinitz' Algorithm: The Original Version and Even's Version |series=Lecture Notes in Computer Science |year=2006 |volume=3895 |publisher=Springer |isbn=978-3-540-32880-3 |pages=218–240 |doi=10.1007/11685654_10 |chapter-url=https://link.springer.com/chapter/10.1007/11685654_10 }}
* {{cite conference |date=2019-04-18 |place=Ben-Gurion University |first1=Ilan |last1=Kadar |first2=Sivan |last2=Albagli |title=Dinitz's algorithm for finding a maximum flow in a network |no-pp=yes |url=https://slideplayer.com/slide/16480683/ |url-status=live |archive-url=https://web.archive.org/web/20231222225209/https://slideplayer.com/slide/16480683/ | archive-date=2023-12-22 }}
* {{cite book |last1=Korte |first1=B. H. |last2=Vygen |first2=Jens |title=Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21) |chapter=8.4 Blocking Flows and Fujishige's Algorithm |year=2008 |publisher=Springer Berlin Heidelberg |isbn=978-3-540-71844-4 |pages = 174–176 }}
* {{cite book |last=Tarjan |first=R. E. |year=1983 |title=Data structures and network algorithms |ref=harv }}

== 関連項目 ==
* [[フォード・ファルカーソン法]]
* [[最大流問題]]

{{最適化アルゴリズム}}

{{DEFAULTSORT:ていにつつほう}}
[[Category:アルゴリズム]]
[[Category:グラフ理論]]
[[Category:数学に関する記事]]