algorithm - Edmonds Karp アルゴリズムと 0 1 容量

Question

使用可能な容量が 0 と 1 のみの場合、エドモンズ カープ (BFS) の上限はいくつですか?

容量が 0 と 1 の場合の違いがわかりません。Ford Fulkerson が、容量が 0 と 1 の場合、フロー値が 0 または 1 であることを発見したことを知っています。これは役に立ちますか?

Answer 1

Edmonds-karp アルゴリズムでは、実行ごとにエッジの 1 つが飽和するため、0 1 またはランダムな容量エッジに違いはありません。両方の実行時間が同じであることを意味し、アルゴリズムも適切に機能します。