問題タブ [edmonds-karp]

Edmonds-Karp アルゴリズムによると、ソース s とシンク t の間の最短距離は、最短経路が拡張されるたびに単調に増加します。この仮定では、ソース s とシンク t の間の距離は |V| 以下になります。- 1. |V| の後、ソース S とシンク T の間にパスがなくなることを意味すると思います。- オーグメンテーション1つ。これが true の場合、最大フローを見つける複雑さは (|V| - 1) * E になります。

上記のことを誤って想定したことはわかっています。しかし、それが何であるかを理解できませんでした。誰でも私を助けることができますか？

フォード・フルカーソンの複雑さは ですO(FE)が、エドモンド・カープの複雑さは ですO(VE^2)。O(V)これは、すべてのエッジがクリティカルな回数だけになるという前提に基づいており、これはすべてのエッジに適用されるためO(VE)、エッジがクリティカルになる可能性のある回数、つまり、拡張パスを見つけることができる回数があります。これは理にかなっています。なぜならO(V)、1 つのエッジだけを利用して何回も費やすことができ、グラフ内の他のすべてのエッジについてもそうするO(VE)必要があるため、拡張パスを見つけるのに必要な時間が得られるからです。次に、BFSテイク が必要O(E)になるため、必要に応じてエドモンズ カープの最終的な複雑さが得られます。

しかし、問題は次のとおりです。O(VE)増補経路の数に関する議論は非常に一般的であるのに、なぜこの分析をフォード・フルカーソンに適用できないのでしょうか? 2 つのアルゴリズムの複雑さが不公平に比較​​されているようです。edmonds karp アルゴリズムが優れている理由は何ですか?

また、edmonds karp で BFS アプローチを使用すると、最短パスを見つけることが保証されるのはなぜですか? これに対する簡単な証明はありますか？