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