algorithm - エッジの追加後に最大フローを更新する

Question

ネットワーク フローがあり、Edmond-Karp アルゴリズムを使用すると、ネットワーク上にすでに最大フローがあるとします。では、任意のエッジ (一定の容量を持つ) をネットワークに追加した場合、最大フローを更新する最良の方法は何ですか? 新しいエッジに関する残差ネットワークを更新し、新しい最大フローが見つかるまで再び拡張パスを探すことを考えていましたが、それが機能するかどうか、またはそれが最善の方法であるかどうかはわかりません!

Answer 1

maxflow を実行すると、各エッジが流れたコンテンツの量がわかります。

したがって、エッジのコストが変更された場合、次のことができます。

1. そのエッジによって流れたコンテンツが であるとしますw。
2. 次に、そのエッジからaforward dfsと aを実行し、リンクされたエッジからコンテンツbackward dfs全体を元に戻します。w

ここで、各エッジは で表されますx/y。ここyで、エッジ容量をx意味し、それが流れたコンテンツを意味します。

次に、エッジのコストを から に変更4->3し2ます3。

あなたがしなければならないことは、フローされたコンテンツとしてこれらのエッジforward and backward dfsから4->3エッジから重みを取り消すことだけです。24->3w=2

プロセスは次のようになります。

これでほぼ完了です:)

3. エッジのコストを4->3からに変更2し3、再び拡張パスを見つけようとします :)

わかりにくい場合や、間違っている場合はお知らせください:)

編集 ：

1. 新しいエッジ コストが現在のコストよりも大きい場合、重みを元に戻す必要はありません。エッジの容量を変更する拡張パスを見つけようとするだけです。

2. ただし、容量が減少した場合は、重量を元に戻して、増加するパスを見つけようとする必要があります.

3. 新しいエッジが追加された場合は、エッジを追加するだけで、利用可能な場合は拡張パスを見つけることができます。それでおしまい。