Ford Fulkerson アルゴリズムは O(|E|f) 時間で実行されます。ここで、f は最大フローです。ただし、O(|E|) を実行する方法はありますか?
O(|E|f) 未満で実行するための解決策の 1 つは、重み付き最短経路問題などを使用して経路を見つけることに関連するものを使用して、フローの最大の増加を可能にする拡張経路を選択することですが、 O(|E|) 時間で実行されることを保証しますか?
基本的に、拡張パスを見つけるために必要な時間の複雑さは無視します (つまり、アルゴリズムが何であれ、複雑さを O(1) とします)。
そのような方法がない場合、反例は何ですか? はいの場合、どのような方法を使用する必要がありますか?