c++ - すべてのパスの長さが同じである場合、Edmonds-Karpの実装を開始するにはどうすればよいですか？

Question

すべてのパスが同じ長さである場合、 Edmonds-Karpアルゴリズムの開始パスを選択するにはどうすればよいですか？この場合、最大フローはパスシーケンスの決定に従って変化します。

Answer 1

頂点での容量の扱い方に問題があると思います。これを行う通常の方法は、頂点 v を 2 つの頂点 v' と v'' に分割し、頂点の容量で v' と v'' の間にエッジを追加することです。v に接続されているすべてのエッジ (つまり、v が宛先である) は、新しいグラフで v' に接続され、v からのすべてのエッジは新しいグラフで v'' から開始する必要があります。

xaby 3 を流すと、リバース エッジの容量が増えることはおそらくご存知でしょう。その場合、エッジ ax 3、ba 3、yb 3 を追加します。説明したようにグラフ表現を行うと、最初のケースで使用できる追加のフローがあることがわかります (xadcby を通過できると思います)。でもチェックしていません）。

最短パスの選択によって答えが変わることはありません。コメントで述べたように、パフォーマンスが低下する悪いケースを避けるために、各ステップで最短パスのみを選択しますが、答えは常に同じです。

この回答がお役に立てば幸いです。