forf fulkersonアルゴリズムで拡張パスを選択する

Question

特定のフローネットワークの残りのネットワークに拡張パスが多数ある場合、ボトルネックキャパシティを最初に見つけるにはどのパスを使用する必要がありますか？

Answer 1

Ford-Fulkerson法では、複数の場合にどの交互パスを使用するか指定しません。
しかし、あなたは、アルゴリズムなど
、その目標変更することができます効率的にパスを増強見つけることができ

• ：ように増強パスを選択します。
• 繰り返し回数が少ない。

Edmonds-Karp（1972）は、拡張パスを選択するための2つの自然なヒューリスティックスを分析しました。増補パスを

• で指定してください。最大のボトルネック値。 （太いパス） - 欲張りアルゴリズム最小値
• アークの数。 （最短パス、BFSを使用して見つけることができます）