【正文】 大流量)(fm a x j。 ST E P0 置初始可行流x（如零流）；對節(jié)點t標(biāo)號，即令)(fm a x t= 任意正值（如 1 ）。 ST E P1 若0)(fm a x ?t，繼續(xù)下一步；否則停止，已經(jīng)得到最大流，結(jié)束。 ST E P2 取消所有節(jié)點Vj ?的標(biāo)號，即令0)(fm a x ?j， 0)(p r e d ?j；令 L I ST = {s} ，對節(jié)點s標(biāo)號，即令?)(fm a x s充分大的正值。 ST E P3 如果 L I ST??且0)(fm a x ?t，繼續(xù)下一步；否則：（ 3 a ）如果t已經(jīng)有標(biāo)號（即0)(fm a x ?t），則找到了一條增廣路，沿該增廣路對流x進行增廣（增廣的流量為)(fm a x t，增廣路可以根據(jù) pr ed 回溯方便地得到），轉(zhuǎn) ST E P 1 。 （ 3 b ）如果t沒有標(biāo)號（即 L I ST =?且0)(fm a x ?t），轉(zhuǎn) S TE P1 。 ST E P4 從 L I ST 中移走一個節(jié)點i；尋找從節(jié)點i出發(fā)的所有可能的增廣?。海?4 a ）對非飽和前向弧),( ji，若節(jié)點j沒有標(biāo)號（即0)(p r e d ?j），對j進行標(biāo)號，即令 },)f(m i n { m a x)(fm a x ijij xuij ??，ij ?)(p r e d， 并將j加入 L I ST 中。 （ 4 b ）對非空后向弧),( ij，若節(jié)點j沒有標(biāo)號（即0)(p r e d ?j），對j進行標(biāo)號，即令 },)f(m i n { m a x)(fm a x ijxij ?，ij ??)(p r e d， 并將j加入 L I ST 中。 例 2：求圖 3中網(wǎng)絡(luò)的最大流。 sba cdt35345 2351圖 3 解：（ 1 ）對所有 ( , )x y E? ，令 ( , ) 0f x y ? ，如圖 a 各邊的第二個數(shù)。 標(biāo) s 為 ),( ??s ，令s? ??。 （ 2 ）對 s 的鄰接點 a 標(biāo) ( , 3 )s ? 。這里因 s 指向 a ，故標(biāo) s的上標(biāo)為 + ，又m in{ ( , ) ( , ) , } m in{ 3 0 , } 3as c s a f s a?? ? ? ? ? ? ? 同理對 s 的鄰接點 b 標(biāo) ( , 4 )s ? 。如圖 a sba cdt3,05,03,045,0 2,03,05,01,0( , )s??( ,3)s?( ,4)s?()a（ 3 ）對與 a 相鄰的點 c ，標(biāo) ( , 3 )a ? ；與 b 相鄰的點 d ，標(biāo) ( , 3 )b ? ； 與 c 相鄰的點 t ，標(biāo) ( , 3 )c ? ，此時 3t? ? ，同時得增廣鏈 s a c t 。如圖 b sba cdt3,05,03,04,05,0 2,03,05,01,0( , )s??( ,3)s?( ,4)s?()b( ,3)a?( ,3)b?( ,3)c?（ 4 ）將邊 ( , ) ( , ) ( , )s a a c c t、 、 各邊的流量增加 3t? ? ，再去掉各點（除s 點）得標(biāo)號，得圖 c sba cdt3,35,33,34,05,0 2,03,04,01,0( , )s??( ,4)s?()c（ 5 ）圖 c 重新標(biāo)號得圖 d ，路 s b d t 為增廣鏈， 3t? ? sba cdt3,35,33,34,05,0 2,03,04,01,0( , )s??( ,4)s?()d( ,3)b?( ,3)d?（ 6 ） 再將此路中各邊得流量增加 3 后刪去標(biāo)號得圖 e sba cdt3,35,33,34,35,0 2,03,34,31,0( , )s??( ,4)s?()e（ 7 ） 同理由（ e ）得（ f ）再得（ g ），由（ g ）得最大流 V a l 7f ? 。 sba cdt3,35,33,34,35,0 2,03,35,31,0( , )s??( ,1)s?()f( ,1)b? ( ,1)a?( ,1)d?( ,1)c?sba cdt3,35,43,34,45,1 2,03,35,41,1()g例 3 用 F or d F ulk e r so n 算法計算如下網(wǎng)絡(luò)中的最大流，每條弧上的兩個數(shù)字分別表示容量和當(dāng)前流量。 最大流問題的推廣 現(xiàn)實問題中的網(wǎng)絡(luò)，不但邊有容量，而且點也有容量。例如運輸網(wǎng)絡(luò)中表示中轉(zhuǎn)站的點v，點容量()cv可表示該中轉(zhuǎn)站能容納的貨物的數(shù)列。對點有容量的網(wǎng)絡(luò)N，流函數(shù)若滿足對一點v，流入v的流量之和等于流出v的流量之和，并且小于等于()cv，則可將N轉(zhuǎn)化為頂點無容量的網(wǎng)絡(luò)問題。方法是： (1) 將點v分成兩個點1v、2v； (2) 作新邊39。 39。39。( , )vv，令39。 39。39。( , ) ( )c v v c v?。 (3) 將 原圖中所有形如( , )xv的邊改為39。( , )xv，所有形如( , )vy的邊改為39。39。( , )vy。 類似可將點x、y以及所有頂點轉(zhuǎn)化為無容量頂點。 最小費用最大流 上面我們介紹了一個網(wǎng)絡(luò)上最短路以及最大流的算法，但是還沒有考慮到網(wǎng)絡(luò)上流的費用問題，在許多實際問題中，費用的因素很重要。例如，在運輸問題中，人們總是希望在完成運輸任務(wù)的同時，尋求一個使總的運輸費用最小的運輸方案。這就是下面要介紹的最小費用流問題。 在運輸網(wǎng)絡(luò)( , , , , )N V E c s t?中，設(shè)( , )w i j、( , )c i j、( , )f i j分別 表示 邊( , )ij的 單位 流 費用 、 容量 和 流量 ，V a l f ??。所謂最小費用流問題就是從發(fā)點到收點怎樣以最小費用輸送一已知量為V a l f ??的總流量。 最小費用流問題可以用如下的線性規(guī)劃問題描述： ( , )m in ( , ) ( , )i j Ew i j f i j?? . : ( , ) : ( , ),( , ) ( , ) 0 , ,j i j E j j i Eisf i j f j i i s tit???????? ? ???????? ， Ajiuf ijij ???? ),(,0. 注： (1) 如果?)( fv最大流)( m axfv，則本問題就是最小費用最大流問題。 (2) 如果)()( m a xfvfv ?，則本問題無解。 求最小費用流的 算 法 — 迭代法 這里所介紹的求最小費用流的方法叫做迭代法。這個方法是由B usac k e r 和 Go wa n 在 1 961 年提出的。其主要步驟如下： ( i ) 求出從發(fā)點到收點的最小費用通路( , )P s t，記該通路的邊集合為()EP。 ( ii ) 對( , )P s t分配最大可能的流量： 0 m in{ ( , ) | ( , ) ( ) }f c x y x y E P??； 對所有的( , ) ( )x y E P?，令0( , ) ( , )c x y c x y f??； 對( , )P s t上的飽和邊，其單位流費用相應(yīng)改為 ? ，且當(dāng)x或ys?或t時，將 該( , )P s t上的飽和邊( , )xy變?yōu)?反向邊( , )yx。令 0( , )c y x f?，( , ) ( , )w y x w x y?? ( iii ) 在這樣構(gòu)成的新網(wǎng)絡(luò)中，重復(fù)上述步驟 ( i ) ， ( ii ) ， 直到從發(fā)點到收點的全部流量等于?為止（或者再也找不到從s到t的最小費用道路）。 此時為最小費用最大流。 例 4 求圖 5 網(wǎng)絡(luò)中的最小費用流。圖中每邊上第一個數(shù)字是容量( , ) ijc i j c? ，第二個數(shù)字是單位流費用 ( , ) ijw i j w? sbact15,417,316,111,2 13,68,214,1圖 5 解：（ 1 ）求 s 到 t 的最小費用通路 s b a t ，如圖 a 。單位費用和1 2 1 4s b ba atw w w? ? ? ? ? ?。 本路徑中可分配的最大流0 11f ?。邊 ( , )ba 飽和。 sbact15,417,316,111,2 13,68,214,1()a2 ） 在 上述 最小 費用 通路 中 的 每邊 的ijc中 減去 11 ， 去掉 邊 ( , )ba ，作 反向邊 ( , )ab ， 且0( , ) , ( , ) 2c a b f w a b? ? ?， 如圖 b 。 在 新 網(wǎng)絡(luò) 中 求 最小 費用 通路 sat ，05 , 3s a s tw w f? ? ?， 邊 ( , )at 飽和 。 sbact15,417,35,111, 2? 13,68,23,1()b（ 3 ）在 sat 路中，每邊的容量減 3 ，atw ??，如圖 c 。求最小費用通路 sbct ，單位流費用和為 6 ，0 5f ?，邊 ( , )sb 飽和。 sbact12,417,35,111, 2?8,20,?()c13,6 （ 4 ） 在 sbct 路 中 ， 每邊 的 容量 減 5 ，sbw ??， 如圖 d 。 求 最小 費用 通路 sabct ， 單位 流 費用 和 為04 ( 2) 3 2 7, 3f? ? ? ? ? ?， 邊 ( , )ct 飽和 。 sbact12,412,30,?11, 2?3,20,?()d13,6 （ 5 ） 在 sabct 路中 ， 每邊 的 容量 減 3 ， sbw ?? ， 如圖 e 。 在 e 中再也 找不到 s 到 t 的 最小 費用 通路 ， 算法 結(jié)束 。 sbact9,49,30,?8, 2? 13,6()e0,?0,?綜合 以上 結(jié)果 ， 網(wǎng)絡(luò) 中 流 的 分配 如圖 f 。 于是 從 s 到 t 的 流 為 ： V a l 11 3 5 3 22f ? ? ? ? ? 最小 費用 為 ： 6 4 14 1 16 1 8 2 8 2 8 3 0 6 110? ? ? ? ? ? ? ? ? ? ? ? ? ? sbact68168 0814()fsbact9,49,30,?8, 2? 13,6()e0,?0,?