algorithm - Dinic のアルゴリズムを使用して、未処理のグラフで最小カット エッジを見つける方法は?

Question

与えられた 2 つのノード 's' と 't' が undiredted グラフで、グラフを 2 つの A と B に分割する最小カット エッジを見つけるアルゴリズムを探しています。's' は A と 't になります。 ' は B になります。

ほとんどの人が Ford-Fulkerson アルゴリズムをそのタスクに使用することを提案しています。Dinic のアルゴリズムを使用することは可能でしょうか。Dinic のアルゴリズムは動的ツリーで高速化できるためです。可能な限り最速の方法で最小カットエッジを見つけたいからです。

巨大な無向グラフで最小カット エッジを見つけるには、どのアルゴリズムがより高速ですか?

これらのアルゴリズムの詳細を検討している間に、アドバイスを聞きたいと思います。

前もって感謝します

Answer 1

基本的に、最大フローを解決するアルゴリズムは、最小カットも解決します。フローを取得したら、残差フロー グラフを見つけます。このグラフでは、ソースsからBFSを実行します。最小カットは、u が s から到達可能で、v が到達できないエッジ( u , v )のセットです。

DinicはFF のΘ(E ² V)とは対照的にO(V ² E)のみであるため、一般的には高速になります。

この場合、残差フロー グラフを見つけて BFS を実行するコストはごくわずかです。