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

建模

程序设计步骤： 程序设计步骤： 对每个节点 j ,其标号包括两部分信息 (pred( j ), max f(j)) 该节点在可能的增广路中的前一个节点 pred( j ) , 以及沿该可能的增广路到该节点为止可 以增广的最大流量 max f ( j ) 。 STEP0 置初始可行流 x(如零流) 对节点 t 标号， ; 即令 max f (t ) =任意正值 (如 1) 。 STEP1 若 max f (t ) > 0 ,继续下一步；否则停止，已经得到最大流，结束。 STEP2 取消所有节点 j ∈ V 的标号，即令 max f ( j ) = 0 ,

pred ( j ) = 0 ;令 LIST={ s },对节点 s 标号，即令 max f ( s ) = 充分大的正值。 STEP3 如果 LIST ≠ Φ 且 max f (t ) = 0 ,继续下一步；否则： (3a)如果 t 已经有标号 则找到了一条增广路，沿该增广路对流 x 进行增广(增广的流量为 max f (t ) ,增广路可以根据得到) ,转 STEP1。 (3b)如果 t 没有标号(即 LIST= Φ 且 max f (t ) = 0 ) ,转 STEP1。 STEP4 从 LIST 中移走一个节点 i ;寻找从节点 i 出发的所有可能的增广弧： (4a) 对非饱和前向弧 (i, j ) ,若节点 j 没有标号(即 pred( j ) = 0 ) ,对 j 进行标号，即令

max f ( j ) = min{max f(i ), uij xij } , pred( j ) = i ,并将 j 加入 LIST 中。 (4b)对非空后向弧 ( j , i ) ,若节点 j 没有标号(即 pred( j ) = 0 ) ,对 j 进行标号， 即令 max f ( j ) = min{max f(i ), xij } , pred ( j ) = i , 并将 j 加入 LIST 中。

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