第2讲 最大流与最小费用流(15)

建模

(A)标号过程： (i) 对任意的弧 e = ( x, y ) ∈ E , f ( x, y ) = 0 ; 置 给发点标号为 ( s , ∞) , 令δs = ∞ ; (ii)若顶点 x 已经标号，则对 x 的所有未标号的邻接顶点 y 按以下规 则标号： ① 若 ( x, y ) ∈ A ,且 f ( x, y ) < c ( x, y ) 时，

令+

δ y = min{c( x, y ) f ( x, y ), δ x } ,则给顶点 y 标号为 ( x , δ y ) ,若 f ( x, y ) = c( x, y ) ,则不给顶点 y 标号。+

② 若 ( y , x ) ∈ A , f ( y , x ) > 0 , δ y = min{ f ( y , x), δ x } , 且 令 则给 y 标号为 ( x , δ y ) ,若 f ( y, x ) = 0 ,则不给 y 标号。

(iii)不断地重复步骤(ii)直到收点 t 被标号，或不再有顶点可以标号 为止。 当 t 被标号时， 表明存在一条从 s 到 t 的可增广轨， 则转向增流过程 (B) 。 如若 t 点不能被标号，且不存在其它可以标号的顶点时，表明不存在从 s 到 t 的可增广轨，算法结束，此时所获得的流就是最大流。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第2讲 最大流与最小费用流(15)在线全文阅读。