フローを最大化するために、C++ でEdmonds-Karpを実装しようとしていましたが、少し違った方法で記述しました。
- 残差グラフのすべてのエッジを調べる代わりに、隣接リストを使用して、元のグラフに存在するエッジのみを調べました。
- 残差グラフを最小フローで更新するときに、バックエッジを更新しませんでした。
興味深いことに、コードを実行すると、正しい結果が得られました。そこで、ウィキペディアの例に行きました。ここでは、バックエッジがどのように使用されているかを具体的に示しています。このグラフをコードに入力すると、再び正しい答えが得られました。結果のフロー マトリックスも確認しましたが、ウィキペディアのものと同じでした。
back-edge を追加および更新する必要がある理由を誰かが説明し、それらが重要な例を挙げてもらえますか?
これが私が書いたコードです（バックエッジを含めるように更新されています）：