グラフに ford-fulkerson 法を適用して最大フローを見つける方法について、順を追って説明しているサイトを教えてください。
よろしくお願いします。
質問する
5794 次
3 に答える
3
私がよく知っている (リンク)、ウィキペディア (リンク)、および最初の代替 Google ヒット (リンク)。
Ford-Fulkerson ラベル付けアルゴリズム
- (初期化) x を初期実行可能フローとする (たとえば、E 内のすべての e に対して x(e) = 0)。
- (フロー拡張) s から t への拡張パスが残差ネットワーク上にない場合は、停止します。現在の x は最大フローです。フロー増加パス p がある場合、フロー x を 2 に置き換えます。
- x(e)=x(e)+delta e が p 上の順方向アークの場合。
- x(e)=x(e)-デルタ e が p 上の後方アークの場合。ここで、デルタは p の残存容量の最小値です。この手順を繰り返します。
ソースコード例: Java
于 2010-11-03T23:40:53.577 に答える
0
また、最小カット定理も興味深いものです。ソースからシンクに流れるフローの最大量は、エッジの最小カットとそのフローに等しくなります。私は学校でその質問にぶつかった:(
于 2013-03-06T00:56:34.680 に答える
0
于 2010-11-03T20:36:50.133 に答える