フォード・フルカーソンの複雑さは です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 アプローチを使用すると、最短パスを見つけることが保証されるのはなぜですか? これに対する簡単な証明はありますか？