ディニックのアルゴリズム
Algorithm for computing the maximal flow of a network

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

歴史

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

アデルソン＝ヴェルスキーのアルゴリズムの授業では、講師が次回の授業で議論する問題を学生に演習問題として与える習慣がありました。DAはこうした演習への対応として考案されました。当時、筆者は[フォード＝フルカーソンアルゴリズム]に関する基本的な事実を認識していませんでした…。

⋮ 無知には時に利点がある。もし著者が飽和エッジの彩度低下の可能性を知っていたなら、DAは当時発明されていなかった可能性が高い。

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

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

意味

を、エッジの容量とフローを とするネットワークとします。 G = ( ( V , E ) , c , f , s , t ) {\displaystyle G=((V,E),c,f,s,t)} c ( u , v ) {\displaystyle c(u,v)} f ( u , v ) {\displaystyle f(u,v)} ( u , v ) {\displaystyle (u,v)}

残留容量は次のように定義される。 c f : V × V → R + {\displaystyle c_{f}\colon V\times V\to R^{+}}
  1. もし、 ( u , v ) ∈ E {\displaystyle (u,v)\in E}
    c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
  2. もし、 ( v , u ) ∈ E {\displaystyle (v,u)\in E}
    c f ( u , v ) = f ( v , u ) {\displaystyle c_{f}(u,v)=f(v,u)}
  3. c f ( u , v ) = 0 {\displaystyle c_{f}(u,v)=0} さもないと。
残差グラフは重み付けされていないグラフであり、 G f = ( ( V , E f ) , c f | E f , s , t ) {\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}
E f = { ( u , v ) ∈ V × V : c f ( u , v ) > 0 } {\displaystyle E_{f}=\{(u,v)\in V\times V\colon \;c_{f}(u,v)>0\}} 。
増加パスは残差グラフ内の-パスです。 s {\displaystyle s} t {\displaystyle t} G f {\displaystyle G_{f}}
をからまでの最短経路の長さと定義します。するとのレベルグラフは のグラフとなり、ここで dist ⁡ ( v ) {\displaystyle \operatorname {dist} (v)} s {\displaystyle s} v {\displaystyle v} G f {\displaystyle G_{f}} G f {\displaystyle G_{f}} G L = ( ( V , E L ) , c f | E L , s , t ) {\displaystyle G_{L}=((V,E_{L}),c_{f}|_{E_{L}},s,t)}
E L = { ( u , v ) ∈ E f : dist ⁡ ( v ) = dist ⁡ ( u ) + 1 } {\displaystyle E_{L}=\{(u,v)\in E_{f}\colon \;\operatorname {dist} (v)=\operatorname {dist} (u)+1\}} 。
ブロッキングフローとは、グラフにパスが含まれないフローのことである。[注 1] [3] s {\displaystyle s} t {\displaystyle t} f ′ {\displaystyle f'} G ′ = ( ( V , E L ′ ) , s , t ) {\displaystyle G'=((V,E_{L}'),s,t)} E L ′ = { ( u , v ) : f ′ ( u , v ) < c f | E L ( u , v ) } {\displaystyle E_{L}'=\{(u,v)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}} s {\displaystyle s} t {\displaystyle t}

アルゴリズム

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

入力: ネットワーク。 G = ( ( V , E ) , c , s , t ) {\displaystyle G=((V,E),c,s,t)}
出力: An –最大値のフロー。 s {\displaystyle s} t {\displaystyle t} f {\displaystyle f}
  1. それぞれに設定します。 f ( e ) = 0 {\displaystyle f(e)=0} e ∈ E {\displaystyle e\in E}
  2. のからを構築します。 の場合、停止して を出力します。 G L {\displaystyle G_{L}} G f {\displaystyle G_{f}} G {\displaystyle G} dist ⁡ ( t ) = ∞ {\displaystyle \operatorname {dist} (t)=\infty } f {\displaystyle f}
  3. でブロッキングフローを見つけます。 f ′ {\displaystyle f'} G L {\displaystyle G_{L}}
  4. フローを増加し、手順 2 に戻ります。 f {\displaystyle f} f ′ {\displaystyle f'}

分析

各ブロッキングフローの層数は毎回少なくとも1ずつ増加するため、アルゴリズムには最大で以下のブロッキングフローが存在することが示されます。それぞれについて、以下のようになります。 | V | − 1 {\displaystyle |V|-1}

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

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

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

特殊なケース

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

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

例

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

G {\displaystyle G} G f {\displaystyle G_{f}} G L {\displaystyle G_{L}}
1.

ブロッキングフローは

  1. { s , 1 , 3 , t } {\displaystyle \{s,1,3,t\}} 4単位のフローで、
  2. { s , 1 , 4 , t } {\displaystyle \{s,1,4,t\}} 6単位のフローで、
  3. { s , 2 , 4 , t } {\displaystyle \{s,2,4,t\}} フロー単位は4です。

したがって、ブロッキング フローは 14 ユニットで、フロー値は14 です。ブロッキング フロー内の各増加パスには3 つのエッジがあることに注意してください。 | f | {\displaystyle |f|}

2.

ブロッキングフローは

  1. { s , 2 , 4 , 3 , t } {\displaystyle \{s,2,4,3,t\}} フローは5単位です。

したがって、ブロッキング フローは 5 ユニットで、フロー値は14 + 5 = 19 です。各増加パスには 4 つのエッジがあることに注意してください。 | f | {\displaystyle |f|}

3.

では に到達できないため、アルゴリズムは終了し、最大値が 19 のフローを返します。各ブロッキング フローで、増加パスのエッジの数が少なくとも 1 増加することに注意してください。 t {\displaystyle t} G f {\displaystyle G_{f}}

参照

注記

  1. ^ これは、飽和エッジ（を持つエッジ）をすべて削除した部分グラフには、からへのパスが含まれないことを意味します。言い換えれば、ブロッキングフローとは、 からへのすべての可能なパスに飽和エッジが含まれるようなフローです。 ( u , v ) {\displaystyle (u,v)} f ′ ( u , v ) = c f | E L ( u , v ) {\displaystyle f'(u,v)=c_{f}|_{E_{L}}(u,v)} s {\displaystyle s} t {\displaystyle t} s {\displaystyle s} t {\displaystyle t}
  2. ^ ブロッキングフローの検出は、一連の前進操作と後退操作によってパスごとに実装できます。詳細については、http://courses.csail.mit.edu/6.854/06/scribe/scribe11.pdf を参照してください。 O ( E ) {\displaystyle O(E)}
  3. ^ 境界では、同じ方向にある同じ頂点のペアを 2 つのエッジが接続しないことを前提としていますが、境界ではそのような前提は設定していません。 O ( V 2 / 3 ) {\displaystyle O(V^{2/3})} O ( E ) {\displaystyle O({\sqrt {E}})}
  1. ^ EA Dinic (1970). 「電力推定を用いたネットワークにおける最大フロー問題の解法アルゴリズム」(PDF) . Doklady Akademii Nauk SSSR . 11 : 1277–1280 .
  2. ^ abc ディニッツ、イェフィム(2006). 「ディニッツのアルゴリズム：オリジナル版とエヴェン版」.オデッド・ゴールドライヒ、アーノルド・L・ローゼンバーグ、アラン・L・セルマン編.理論計算機科学：シモン・エヴェン追悼エッセイ集. 計算機科学講義ノート. 第3895巻. シュプリンガー. pp.  218– 240. doi :10.1007/11685654_10. ISBN 978-3-540-32880-3。
  3. ^ ab Tarjan 1983、p. 102を参照。
  4. ^ Even, Shimon; Tarjan, R. Endre (1975). 「ネットワークフローとグラフ接続性のテスト」. SIAM Journal on Computing . 4 (4): 507– 518. doi :10.1137/0204043. ISSN  0097-5397.

参考文献

Retrieved from "https://en.wikipedia.org/w/index.php?title=Dinic%27s_algorithm&oldid=1258607582"