algorithm - 個別のパスの最大数を見つけるためのベルマンフォードまたはネットワークフロー?

Question

sの入次数と出次数が に等しい2 つの頂点を持つ有向グラフ (重みなし) G(V, E) がtありsます。からへの個別エッジ パスの最大数を見つけたいとします。どのアルゴリズムを使用してこれを行うことができます。Bellman-Ford、Dijkestra、Huffman、および Network Flow。ハフマンはあまり関係ないと思いますが、他の人はどうですか？ネットワーク フローが答えだと思いますが、その理由がわかりません。スタックキーアー、助けてください！t0st

Answer 1

ネットワークフローでそれを行うことができます。ウィキペディアで方法を教えてくれます：

最大エッジ独立パス

有向グラフ G = (V, E) と 2 つの頂点 s と t が与えられた場合、s から t へのエッジ独立パスの最大数を見つける必要があります。この問題は、s と t をそれぞれ N のソースとシンクとして、G からネットワーク N = (V, E) を構築し、各エッジに単位容量を割り当てることによって、最大フロー問題に変換できます。

この背後にある直感は、最大フロー アルゴリズムは基本的に、増加パスを見つけながら問題を解決するということです。拡張パスとは何かについては、 Ivaylo Strandjevによるこの SO の質問で最もよく説明されています。

増補パスは、ソースからシンクまでの正の容量を持つエッジのみを使用して、グラフを通過する単純なパス (サイクルを含まないパス) です。したがって、上記のステートメントはどういうわけか明白です-正の容量エッジのみを使用するソースからシンクへのパスを見つけることができない場合、フローを増やすことはできません(ちなみに、そのステートメントの証明はそれほど簡単ではありません)。