ディニックのアルゴリズム

ディニックのアルゴリズムまたはディニッツのアルゴリズムは、フローネットワークの最大フローを計算するための強力な多項式アルゴリズムであり、1970年にイスラエル（旧ソ連）のコンピュータ科学者イェフィム・ディニッツによって考案されました。^[1]このアルゴリズムは時間内で実行され、最短増加パスを使用する点で、時間内で実行されるエドモンズ-カープアルゴリズムに似ています。レベルグラフとブロッキングフローの概念の導入により、ディニックのアルゴリズムはそのパフォーマンスを実現できます。 ${\displaystyle O(|V|^{2}|E|)}$${\displaystyle O(|V||E|^{2})}$

ディニッツは1969年1月に、ジョージ・アデルソン＝ヴェルスキーのグループの修士課程の学生としてこのアルゴリズムを発明した。数十年後、彼は次のように回想している。^[2]

Adel'son-Vel'sky のアルゴリズムの授業では、講師が次回の会議で議論する問題を学生に演習として与える習慣がありました。DA はそのような演習に応じて発明されました。当時、著者は [ Ford-Fulkerson アルゴリズム] に関する基本的な事実を認識していませんでした…。

⋮

無知には時には利点があります。飽和エッジの彩度を下げるというアイデアが著者に知られていたなら、DA は当時発明されなかった可能性が高いでしょう。

1970年、ディニッツはDoklady Akademii Nauk SSSRでアルゴリズムの説明を発表しました。1974年、ハイファ工科大学のシモン・エヴェンと（当時は博士課程の学生だった）アロン・イタイは、ディニッツのアルゴリズムと、アレクサンダー・V・カルザノフの関連するブロッキングフローのアイデアに非常に興味を持ち、魅了されました。しかし、ジャーナルDoklady Akademii Nauk SSSRの制限を満たすために、これら2つの論文はそれぞれ4ページに制限されており、解読するのは困難でした。エヴェンはあきらめず、3日間の努力の末、階層化ネットワークのメンテナンスの問題を除いて両方の論文を理解することができました。その後数年間、エヴェンは「ディニッツのアルゴリズム」に関する講義を行い、著者の名前を間違って発音しながらそれを広めました。エヴェンとイタイは、BFSとDFSを組み合わせることでこのアルゴリズムにも貢献しました。これが、現在このアルゴリズムが一般的に提示されている方法です。^[2]

フォード・ファルカーソン アルゴリズムが発明されてから約 10 年間、無理辺容量の一般的なケースでこのアルゴリズムが多項式時間で終了するかどうかは不明でした。このため、一般的なケースで最大フロー問題を解決するための多項式時間アルゴリズムは知られていませんでした。ディニッツのアルゴリズムとエドモンズ・カープ アルゴリズム(1972 年に公開) はどちらも独立して、フォード・ファルカーソン アルゴリズムでは、各増加パスが最短パスである場合、増加パスの長さは減少せず、アルゴリズムは常に終了することを示しました。

を、エッジの容量とフローをとするネットワークとします。 ${\displaystyle G=((V,E),c,f,s,t)}$${\displaystyle c(u,v)}$${\displaystyle f(u,v)}$${\displaystyle (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 s}$${\displaystyle t}$${\displaystyle G_{f}}$

をからまでの最短経路の長さと定義します。すると のレベルグラフは のグラフとなり、ここで ${\displaystyle \operatorname {dist} (v)}$${\displaystyle s}$${\displaystyle v}$${\displaystyle G_{f}}$${\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\}}$。

ブロッキングフローとは、グラフにパスが含まれないフローのことである。^{[注 1] [3]}${\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}$

ディニックのアルゴリズム

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

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

1. それぞれに設定します。${\displaystyle f(e)=0}$${\displaystyle e\in E}$
2. のから構築します。 の場合、停止して を出力します。${\displaystyle G_{L}}$${\displaystyle G_{f}}$${\displaystyle G}$${\displaystyle \operatorname {dist} (t)=\infty }$${\displaystyle f}$
3. でブロッキングフローを見つけます。${\displaystyle f'}$${\displaystyle G_{L}}$
4. フローを拡張して、手順 2 に戻ります。${\displaystyle f}$${\displaystyle f'}$

各ブロッキング フローのレイヤー数は毎回少なくとも 1 ずつ増加し、アルゴリズムには最大でブロッキング フローが存在することがわかります。それぞれについて、次のようになります。 ${\displaystyle |V|-1}$

• レベルグラフは、時間的に幅優先探索によって構築できる。${\displaystyle G_{L}}$${\displaystyle O(E)}$
• レベルグラフのブロッキングフローは時間内に見つかる^[注2]${\displaystyle G_{L}}$${\displaystyle O(VE)}$

各層の合計実行時間は である。結果として、Dinicのアルゴリズムの実行時間は である。^[2]${\displaystyle O(E+VE)=O(VE)}$${\displaystyle O(V^{2}E)}$

動的ツリーと呼ばれるデータ構造を使用すると、各フェーズでブロッキングフローを見つける実行時間を まで短縮できるため、Dinic のアルゴリズムの実行時間を まで改善できます。 ${\displaystyle O(E\log V)}$${\displaystyle O(VE\log V)}$

ユニット容量を持つネットワークでは、はるかに強い時間制限が適用されます。各ブロッキングフローは時間内に見つけることができ、フェーズの数がを超えないことが示されます。^[注3]したがって、アルゴリズムは時間内に実行されます。^[4 ]${\displaystyle O(E)}$${\displaystyle O({\sqrt {E}})}$${\displaystyle O(V^{2/3})}$${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$

二部マッチング問題から生じるネットワークでは、フェーズの数は によって制限されるため、時間制限が導かれます。結果として得られるアルゴリズムは、ホップクロフト・カープアルゴリズムとしても知られています。より一般的には、この制限は任意の単位ネットワーク、つまりソースとシンクを除く各頂点が容量 1 の単一の入力エッジ、または容量 1 の単一の出力エッジを持ち、他のすべての容量が任意の整数であるネットワークに当てはまります。^[3]${\displaystyle O({\sqrt {V}})}$${\displaystyle O({\sqrt {V}}E)}$

以下は、Dinic のアルゴリズムのシミュレーションです。レベル グラフでは、赤いラベルの付いた頂点が値です。青いパスはブロッキング フローを形成します。 ${\displaystyle G_{L}}$${\displaystyle \operatorname {dist} (v)}$

• フォード・フルカーソンアルゴリズム
• 最大流量問題

• ディニッツ、イェフィム(2006)。「ディニッツのアルゴリズム: オリジナル版とエヴェン版」。オデッド・ゴールドライヒ、アーノルド・L・ローゼンバーグ、アラン・L・セルマン(編)。理論計算機科学:シモン・エヴェンを偲んで。計算機科学講義ノート。第 3895 巻。シュプリンガー。pp. 218–240。doi : 10.1007/11685654_10。ISBN 978-3-540-32880-3。
• Kadar, Ilan; Albagli, Sivan (2019年4月18日). ネットワーク内の最大フローを見つけるためのDinitzのアルゴリズム。ベングリオン大学。2023年12月22日時点のオリジナルよりアーカイブ。
• Korte, BH; Vygen, Jens (2008)。「8.4 ブロッキングフローと藤重のアルゴリズム」。組み合わせ最適化: 理論とアルゴリズム (アルゴリズムと組み合わせ論、21)。Springer Berlin Heidelberg。pp. 174–176。ISBN 978-3-540-71844-4。
• Tarjan, RE (1983).データ構造とネットワークアルゴリズム.