algorithm - ford fulkerson アルゴリズムの bfs の変更、拡張パスを見つける

Question

私はbfsを使用して拡張パスを見つけていますが、毎回同じパスを生成しています.しかし、フォードフルカーソンアルゴリズムでは、ソースからシンクへの毎回異なるパスを選択する必要があります. source と sink.graph の間の毎回のパスが指示され、重み付けされます

Answer 1

すべての容量が使用されているエッジを BFS が無視するようにする必要があります。通常、BFS はいわゆるResidual Networkで実行されます。各エッジ キャパシティは、そのエッジにどれだけのキャパシティが残っているかを示します (そのエッジを介して送信したフローが与えられます)。別の残差グラフを維持するか、BFS に各エッジの元の容量と現在のフローの差を調べさせることで暗黙的なグラフを作成することができます (そして、容量がゼロの場合はエッジが存在しないものとして処理します)。