【正文】 0 ,T ( v 2 ) =1 ( b ) P ( v 1 ) =0 ,P ( v 2 ) =1T ( v 3 ) =4 T ( v 3 ) =3 ,T ( v 4 ) =4 v 2 + ? v 2 + ?v 1 v 1v 3 v 6 v 3 v 6( c ) P ( v 1 ) =0 ,T ( v 2 ) =1 ( d ) P ( v 1 ) =0 ,P ( v 2 ) =1 P ( v 3 ) =3 ,T ( v 4 ) =4 ， T ( v 6 )= 5 P ( v 3 ) =3 ,P ( v 4 ) =4 ， T ( v 6 ) =563 v 2 v 5v 1v 3 v 6( e ) P ( v 1 ) =0,P ( v 2 ) =1 P ( v 3 ) =3,P ( v 4 ) =4 P ( v 6 ) =5（圖 10） 此時仍有 T標號點 v5不能改為 P標號 ， 說明不存在從 v1到 v5的路 ， 所以計算終止 。 圖 (e)中各方框的數(shù)字表示從 v1到各點的最短路長 。 D氏標號法只適用于全部權(quán)為非負情況 。 如果網(wǎng)絡中含有負權(quán)的弧 ， 則算法失效 ， 應改用其它算法 。 64 二、求網(wǎng)絡中任意兩點意最短路的 Floyd算法 對求網(wǎng)絡中任意兩點間的最短路 ， 當然可用改變起始點的辦法 ， 采用 D氏標號法達到目的 ， 但顯然較繁 。 Floyd算法卻可直接求出網(wǎng)絡中任意兩點間的最短路 ， 且 wij的正負不受限制 。 Floyd方法的具體步驟如下： 開始 (k=0)， 作距離矩陣 L(o)=(Lij(o))和序號矩陣 ?(o)=(?ij(o)) 其中 ???????AvvL jiijoij),()( ? ? ij ( o ) = j ( i , j = 1 , 2 , ? p) 第一步： k=r(1?r?p)時， L(k)中第 k行和第 k列元素保持不變，其它元素按下式計算，并填入 L(k)=(Lij(k))中： 65 L ij ( k) = m i n { L ij ( k 1 ) , L ik ( k 1 ) + L kj ( k 1 ) } ( 4 . 2 )相應地， ?(k)的各元素按下式變化： ?????????? ????)1()()1()1()()1()(,kijkijkikkijkijkijkij LLLL若若() 第二步：若存在 Lii0(1?i?p)， 計算終止 ， 即說明 D中存在一條含有頂點 vi的負回路 Q， (即 dii=W(Q)0的回路 )， 并由 ?ij(k)(i,j=1,2,… p)， 找出此回路 。 否則 ， 置 k=k+1。 第三步：當 k=p， 計算終止 。 若 Lij(p)=+?， 則說明 D中不存在從 vi到 vj的路；否則 ， 記 dij=Lij(p)， 表示由 vi到 vj的最短路長 ， 相應的最短路可由 ?ij(p)(i,j=1,2,… p)找出 。 66 例 用 Floyd方法求圖 11中各頂點間的最短路，其中?。ㄟ叄┡缘臄?shù)字表示弧（邊）長。 V 2 （圖 11 ）176。v 3v 5v 1v 4 432334 19 解： k=0， 把圖 11中的兩條邊看作長度相等 ， 方向相反的兩條弧 。 即有 ?14=?41=9， ?25=?52=2。 根據(jù)圖 11中的數(shù)據(jù)， 作 L(o)=(Lij(o))同時作 ?(0)=(?ij(o))， 如表中 k=0所示 。 k=1， 將 L(1)中第 1行和第 1列的元素保持不變 （ 在表中用虛線將其覆蓋 ） ， 其它元素按 ()式進行計算 ， 例如 67 L42(1)=min{L42(o),L41(o)+L12(o)}=min{?,9+3}=12 L43(1)=min{L43(o),L41(o)+L13(o)}=min{?,9+4}=13 其余元素經(jīng)計算不變 。 對更新數(shù)字的元素均加上圓圈 。 同時 ， 在 k=1的序數(shù)矩陣中 ， 按 ()式有 ?42( 1 ) =?41( o)=1，?43(o)=?41(o)=1， 并加上圓圈 。 如表中 k=1所示 。 k=2， 將 L(2)的第 2行和第 2列的元素保持不變 ， 按 ()式計算： L13(2)=min{L13(1),L12(1)+L23(1)}=min{4,3+(4)}=1 L15(2)=min{L15(1),L12(1)+L25(1)}=min{?,3+2}=5 L43(2)=min{L43(1),L42(1)+L23(1)}=min{13,12+(4)}=8 L53(2)=min{L53(1),L52(1)+L23(1)}=min{?,2+(4)}=2 其余元素未變 ， 并對 L13(2)， L15(2)， L43(2)， L53(2)加圈 。 同時在 ?(2)中 ,按 ()式有 ?13(2)=?12(1)=2,?15(2)=?12(1),?43(2)=?42(1)=1,?53=?52(1)=2， 并加圈 。 如表中 k=2所示 。 k=3,4,5的結(jié)果均在表中給出 ， 過程從略 。 68 L(5)=(Lij(5))給出了圖 11中各點之間的最短路長，?(5)=(?ij(5))給出了從 vi到 vj的最短路必須經(jīng)過點的下標，并由此可找出最短路。例如從 v1到 v5的最短路長為 1(L15(5)=1),最短路由 ?15(5)=2（即必經(jīng)過 v2）， 又由 ?25(5)=3（即經(jīng)過 v3），再由 ?35(5)=4（即必經(jīng)過 v4）， 最后由 ?45(5)=5,可知從 v1到 v5的最短路是 (v1,v2,v3,v4,v5)。 同樣，從 v5到 v1的最短路長為 10，最短路為 (v5,v2,v3,v4,v1)。 表k=0 k=1 k=2 k=3 k=4 k=5[L ij( k)]021093302409430????????????0210131293302409430??????????02210812933024059130??????????0122108129330114022130??????????01221010812923015122140812130??????012210103192304122140812130???????[ ? ij( k)]54321543215432154321543215432154111543215432154321542215411154321543212422152221541115432133321222215222254111443443332322221522225455144344333232222169 例 用 Flogd方法求圖 12中各頂點之間的最短路，其中各弧旁的數(shù)據(jù)表示弧長。 V1。 V2。 V4。 V3。 2 1 2 2 2 2 6 6 （圖 12） 解： k=0， 由 L(o)=[lij(o)]和?(o)=[?ij(o)],按 ()式計算及按 ()式得表 62(k=0,1,2)如下： 70 表 6 —2k =0 k =1 k =2[L ij( k)]062260222010????????061260222010?????????36124022201310??????????[ ? ij( k)]432143214321432143114321432143211311232143212221 由于 L44(2)=30， 說明圖 12中含有頂點 v4的負回路 Q，由 [?ij(2)]中的 ?44(2)=1, ?14(2)=2, ?24(2)=4可知，負回路Q={v4,v1,v2,v4}， d44=L44(2)=3， 計算終止。否則，繼續(xù)計算下去，則會出現(xiàn)更多的負回路，且隨著計算次數(shù)增多，含有負回路 P的長 dij??。 因此，本題不存在從 vi到 vj的最短路(i,j=1,2,3,4)。 71 167。 4. 最大流問題 最大流問題是一類極為廣泛的問題。不僅在交通運輸網(wǎng)絡中有人流、車流、貨物流、供水網(wǎng)絡中有水流、金融系統(tǒng)中有現(xiàn)金流、通訊網(wǎng)絡中信息流 …… 等。五十年代，F(xiàn)ord(福特 )、 Fulkerson(富克遜 )建立的“網(wǎng)絡流理論”，是網(wǎng)絡應用的重要組成部分。 一、網(wǎng)絡與流的概念 對于有向圖 D=(V,A)， 如果 V中有一發(fā)點 vs（ 亦稱源還有一收點（亦稱為匯）記為 vt， 其余均為中間點，且對 A中的每條弧均有權(quán) W(vi,vj)?0（ 簡記為 Wij， 并稱為弧容量），則稱這樣的賦權(quán)有向圖 D為容量網(wǎng)絡，記為 D=(V,A,W)。 通過D中弧 (vi,vj)的物流量 fij， 稱為弧 (vi,vj)的流量。所有弧上流量的集合 f={fij}稱為該網(wǎng)絡 D的一個流。 72 在圖 13中，弧旁括號中的兩個數(shù)字 (Wij,fij)， 第 1個數(shù)字表示弧容量，第二個數(shù)字表示通過該弧的流量?；?(vs,v1)上的 (8,6)，前者是弧容量，表示可通過該弧最大流量的能力為 8，后者是目前通過該弧的實際流量為 6。 v 1 v 4 v 2 v 3 （圖 13 ） ? ? ? ? ? ? v t v s ( 1 0 , 5 ) ( 3 , 3 ) ( 8 , 6 ) ( 6 , 1 ) ( 6 , 2 ) ( 4 , 2 ) ( 5 , 4 ) ( 7 , 3 ) ( 5 , 4 ) 從圖 13中可見 ：（ 1） 通過每弧的流量均不超過弧容量（ 2） 發(fā)點 vs流出的總量為 6+3=9,等于流入收點 vt的總量5+4=9；（ 3） 各中間點的流出量等于其流入量。各中間點v2的流出量減去其流入量等于 0,即 4－ (3+1)=0 73 一般地 ， 在容量網(wǎng)絡 D=(V,A,W)中 ， 滿足以下條件的流f， 稱為可行流： （ 1） 弧流量限制條件 0?fij?cij (vi,vj)?A （ 2） 平衡條件 ? ????????????i jjiijtiftsiOsifff當當當)(,)(vv 式中 v(f)為該可行流的流量，即發(fā)點的凈輸出量，或收點的凈輸入量。對于網(wǎng)絡的流，可行流總是在存在的。如 f={0}。 74 二、最大流問題 最大流問題就是在容量網(wǎng)絡 D中，求一個可行流 f={fij}，使其流量 v(f)達到最大。其數(shù)學模型為 m a x v ( f ) 滿足????????????????????? ?tifvtsiOsifvffAvvcfOjiijjiijij)(,)(),( 顯然，最大流問題是個特殊的 LP問題可用單純形法或表上作業(yè)法求解，但利用它與圖的緊密關(guān)系，能更為直觀簡便地求解。 75 三、求網(wǎng)絡最大流的有關(guān)概念與原理 。 設 D=(V,A,C)中 ， 有一可行流 f={fij}， 按每條弧上流量的多少 ， 可將弧分四種類型： 飽和弧 (即 fij=wij) 非飽和弧 (即 fijwij) 零流弧 (即 fij=0) 非零流弧 (即 fij0) 如圖 13中 ， (v1,v4)是飽和弧 ， 又是非零流弧 ， 其它各弧均為非飽和弧 ， 也是非零流弧 。 設 ?是 D中從 vs別 vt的一條鏈 ， 沿此方向 ， 鏈上各弧可分為兩類： 正向弧 （ 與鏈的方向一致的弧 ） ， 其集合記為 ?+