【文章內(nèi)容簡(jiǎn)介】 10 2 3 1 2 6 2 4 10 1 (5,2) (10,5) (6,2) (9,5) (12,5) (0,0) (3,1) (1,1) v1 v4 v2 v8 v7 v6 v5 v9 6 3 6 2 3 4 10 2 3 1 2 6 2 4 10 1 (5,2) (10,5) (6,2) (9,5) (12,5) (0,0) (3,1) (1,1) v1 v4 v2 v8 v7 v6 v5 v9 6 3 6 2 3 4 10 2 3 1 2 6 2 4 10 1 (5,2) (10,5) (6,2) (9,5) (12,5) (0,0) (3,1) (1,1) v1 v4 v2 v8 v7 v6 v5 v9 6 3 6 2 3 4 10 2 3 1 2 6 2 4 10 1 (5,2) (10,5) (6,2) (9,5) (12,5) 從 v1 到 v8 的最短路的長(zhǎng)度為： 12 從 v1 到 v8 的最短路線為： v8 v5 v2 v1 步驟： 給起點(diǎn)一個(gè)永久標(biāo)號(hào) （ 0， 0） 。永久標(biāo)號(hào)用下劃線表示；標(biāo)號(hào)中的第一個(gè)數(shù)表示從起點(diǎn)到該點(diǎn)的距離；第二個(gè)數(shù)表示該點(diǎn)的前面沒(méi)有點(diǎn)了。 修改非永久標(biāo)號(hào)點(diǎn) vi 的臨時(shí)標(biāo)號(hào)為 (a,b), 其中 a 為以 vi 為終點(diǎn)的弧，如果其起點(diǎn)為永久標(biāo)號(hào)，則求其永久標(biāo)號(hào)的第一個(gè)數(shù)與弧長(zhǎng)的和，如果這樣的和有多個(gè)，則取最小值。b為前一個(gè)點(diǎn)的下標(biāo)。 在臨時(shí)標(biāo)號(hào)中取第一個(gè)標(biāo)號(hào)的最小值，將該標(biāo)號(hào)該為永久標(biāo)號(hào)，再返回到 2步 三、含有負(fù)權(quán)的最短路的求法 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 例： 求從 v1 到 v8 的最短路 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 1 2 3 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 1 1 5 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 1 1 5 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 3 1 5 6 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 3 1 5 6 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 3 1 5 6 8 3 2 6 1 3 5 1 1 2 1 2 1 1 7 3 3 v1 v2 v3 v4 v5 v6 v7 v8 0 5 2 7 3 1 5 6 從 v1 到 v8 的最短路的長(zhǎng)度為： 6 從 v1 到 v8 的最短路線為： v8 v6 v3 v1 167。 最小費(fèi)用流問(wèn)題 一 引言 在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問(wèn)題 。 例如鐵路運(yùn)輸系統(tǒng)中的車(chē)輛流 ， 城市給排水系統(tǒng)的水流問(wèn)題等等 。 而網(wǎng)絡(luò)系統(tǒng)流最大流問(wèn)題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問(wèn)題 ， 它對(duì)于解決生產(chǎn)實(shí)際問(wèn)題起著十分重要的作用 。 圖 vs和目的地 vt的交通運(yùn)輸網(wǎng) ， 每一條弧 vi 旁邊的權(quán) cij表示這段運(yùn)輸線的最大通過(guò)能力 ， 貨物經(jīng)過(guò)交通崗從 vs運(yùn)送到 ， 使得從 vs到vt的貨運(yùn)量最大 ， 這個(gè)問(wèn)題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 。 ?問(wèn)題描述 連通網(wǎng)絡(luò) G(V, A) 有 m 個(gè)節(jié)點(diǎn) , n條弧 , 弧 eij 上的流量上界為 cij, 求從起始節(jié)點(diǎn) vs 到終點(diǎn) vt 的最大流量。 圖 vt v3 v2 v1 v4 vs 17 3 5 10 8 6 11 4 5 3 Cij 二 基本概念 定義 設(shè)一個(gè)賦權(quán)有向圖 D=（ V,A） ,在 V 中指定一個(gè)發(fā)點(diǎn) vs和一個(gè)收點(diǎn) vt ,其它的點(diǎn)叫做中間點(diǎn) 。 對(duì)于 D中的每一個(gè)弧 （ vi ,vj）∈ A,都有一個(gè) 權(quán) 叫做弧的 容量 。 我們把這樣的圖 D叫做一個(gè) 網(wǎng)絡(luò)系統(tǒng) ， 簡(jiǎn)稱(chēng)網(wǎng)絡(luò) ， 記做D=（ V， A， C） 。 網(wǎng)絡(luò) D上的流 ， 是指定義在弧集合 A上的一個(gè)函數(shù) f={f(vi ,vj)}={fjj} f(vi ,vj)=fij叫做弧 (vi ,vj)上的流量 。 例如圖 。 每一個(gè)弧旁邊的權(quán)就是對(duì)應(yīng)的容量 （ 最大通過(guò)能力 ） cij . 圖 （運(yùn)輸方案），每一個(gè)弧上的流量 fij就是運(yùn)輸量。例如 fs1=5 , fs2=3 , f13=2 等等。 對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流 ， 有幾個(gè)顯著的特點(diǎn)： (1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等 。 (2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零 。 (3)每一個(gè)弧上的流量 不能超過(guò)它的最大通過(guò)能力（即容量） 于是有： v3 v2 v1 v4 vs （ 2） （ 3） （ 2） （ 5） （ 3） （ 3） （ 6） （ 1） （ 1） （ 2） fij vt 圖 定義 網(wǎng)絡(luò)上的一個(gè)流 f 叫做可行流 ，如果 f 滿足以下條件 （ 1） 容量條件： 對(duì)于每一個(gè)弧 （ vi ,vj）∈ A,有 0 ? fij ? cij . （ 2） 平衡條件： ? ?? ???Avv Avvsjjsjs sjfvff),( ),()(對(duì)于發(fā)點(diǎn) vs,有 對(duì)于收點(diǎn) vt,有 ? ?? ????Avv Avvtjjtjt tjfvff),( ),()(對(duì)于中間點(diǎn) ， 有 ? ?? ???Avv Avvijjiji ijff),( ),(0 任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流 v(f)=0,就是滿足以上條件的可行流。 網(wǎng)絡(luò)系統(tǒng)中最大流問(wèn)題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流 f,其流量 v(f)達(dá)到最大值。 設(shè)流 f ={fij}是網(wǎng)絡(luò) D上的一個(gè)可行流。我們把 D中 fij=cij的弧叫做飽和弧， fijcij的弧叫 其中發(fā)點(diǎn)的總流量 （ 或收點(diǎn)的總流量 ） v ( f ) 叫做這個(gè)可行流的流量 。 做非飽和弧， fij0的弧為非零流弧， fij=0的弧 叫做零流弧 . 在圖 ， (v4 ,v3)是飽和弧 ， 其他的弧是非飽和弧 ， 并且都是非零流弧 。 設(shè) μ是網(wǎng)絡(luò) D中連接發(fā)點(diǎn) νs和收點(diǎn) vt的一條鏈 。 定義鏈的方向是從 νs到 vt ， 于是鏈 μ上的弧被分為兩類(lèi)：一類(lèi)是弧的方向與鏈的方向相同 ， 叫做前向弧 ， 前向弧的集合記做 μ+。 二類(lèi)是弧的方向與鏈的方向相反 ， 叫做后向弧 ， 后向弧的集合記做 μ–。 例如在圖 ， 在鏈 （ vs,v1,v2,v3,v4,vt)中 ， μ+ = {vs,v1,(v1,v2),(v2,v3),(v4,vt)}, μ – = {(v4 ,v3)}. 增廣鏈： 如果鏈 μ滿足以下條件： 1． 在弧 （ vi ,vj） ∈ μ+上 ， 有 0?fijcij,即 μ+中的每一條弧是非飽和弧 。 2． 在弧 （ vi,vj） ∈ μ–上 ， 有 0fij?cij,即 μ–中的每一條弧是非零流弧 。 例如在圖 ， 鏈 μ=（ vs,v1,v2,v3,v4,vt） 就是一條增廣鏈 。 設(shè)圖 D=(V， A， C)， 點(diǎn)集 S， T?V,S∩T=ф。將起點(diǎn)在 S， 終點(diǎn)在 T 的所有弧作成集合 ， 記做 （ S， T） 。 定義 設(shè)一個(gè)網(wǎng)絡(luò) D=（ V， A， C） 。如果點(diǎn)集 V 被剖分為兩個(gè)非空集合 v1和 ，發(fā)點(diǎn) vs∈ v1,收點(diǎn) vt∈ ,那么將弧集 （ v1 ， ）叫做是分離 vs和 vt的截集 。 1V1V1V 定義 設(shè)一個(gè)截集 （ V1 , ） .將階截集（ V1 , ） 中所有的弧的容量的和叫做截集的截量 ， 記做 s( V1 , ) , 亦即 1V1V1V? ? ???),(),(,1111VVvvjijicVVs下面的事實(shí)是顯然的：一個(gè)網(wǎng)絡(luò) D中，任何一個(gè)可行流 f 的流量 v (f ) 都小于或等于這個(gè)網(wǎng)絡(luò)中任何一個(gè)截集 (V1 , )的截量。并且，如果 1V網(wǎng)絡(luò)上的一個(gè)可行流 f * 和網(wǎng)絡(luò)中的一個(gè)截集（ V1*, ） ，滿足條件 v*(f* )=c (V1* , ) ,那么 f * 一定是 D上的最大流，而 （ V1*, ） 一定是 D的所有的截集中截量最小的一個(gè)（即最小截集） *1V*1V*1V 定理 網(wǎng)絡(luò)中的一個(gè)可行流 f*是最大流的充分必要條件是，不存在關(guān)于 f*的增廣鏈。 定理 在一個(gè)網(wǎng)絡(luò) D中，最大流的流量等于分離 vs 和 vt 的最小截集的截量。 定理 統(tǒng)最大流的方法。亦即，如果網(wǎng)絡(luò) D中有一個(gè)可行流 f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流 f 的增廣鏈 。如果沒(méi)有增廣鏈，那么 f一定是最大流。如有增廣鏈，那么可以按照定理 ，不斷改進(jìn)和增大可行流 f 的流量，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。 三 ． 標(biāo)號(hào)法 從網(wǎng)絡(luò)中的一個(gè)可行流 f 出發(fā) （ 如果 D中沒(méi)有 f， 可以令 f 是零流 ） ， 運(yùn)用標(biāo)號(hào)法 ，經(jīng)過(guò)標(biāo)號(hào)過(guò)程和調(diào)整過(guò)程 ， 可以得到網(wǎng)絡(luò)中的一個(gè)最大流 。 下面用給頂點(diǎn)標(biāo)號(hào)的方法來(lái)定義 V1*.在標(biāo)號(hào)過(guò)程中 ， 有標(biāo)號(hào)的頂點(diǎn)是 V1*中的點(diǎn) ，沒(méi)有標(biāo)號(hào)的點(diǎn)不是 V1*中的點(diǎn) 。 如果 vt有了標(biāo)號(hào) ， 表示存在一條關(guān)于 f 的增廣鏈 。 如果標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去 ， 并且 vt未被標(biāo)號(hào) ， 則表示不存在關(guān)于 f 的增廣鏈 。 這樣 ， 就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集 。 1． 標(biāo)號(hào)過(guò)程 在標(biāo)號(hào)過(guò)程中 ， 網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號(hào)點(diǎn) （ 分為已檢查和未檢查兩種 ） 。 或者是未標(biāo)號(hào)點(diǎn) 。 每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的 。以便找出增廣鏈 。 第二個(gè)標(biāo)號(hào)是為了用來(lái)確定增廣鏈上的調(diào)整量 θ。 標(biāo)號(hào)過(guò)程開(kāi)始 ， 先給 vs 標(biāo)號(hào) （ 0， +∞） 。這時(shí) ， vs 是標(biāo)號(hào)未檢查的點(diǎn) ， 其它都是未標(biāo)號(hào)點(diǎn) 。 一般地 ， 取一個(gè)標(biāo)號(hào)未檢查點(diǎn) vi， 對(duì)一切未標(biāo)號(hào)點(diǎn) vj ： （ 1） 如果在弧 （ vi ,vj） 上 ， fijcij,那么給 vj 標(biāo)號(hào) （ vi ,l(vj) ） .其中 l(vj) = min[l(vi),cij – fij].這時(shí) ， vj 成為標(biāo)號(hào)未檢查的點(diǎn) 。 （ 2） 如果在弧 （ vj ,vi） 上 ， fji 0,那么給vj標(biāo)號(hào) （ vi , l(vj)） .其中 l (vj)=min[ l(vi), fji ].這時(shí) ， vj 成為標(biāo)號(hào)未檢查點(diǎn) 。 于是 vi 成為標(biāo)號(hào)已檢查的點(diǎn) 。 重復(fù)以上步驟 ， 如果所有的標(biāo)號(hào)都已經(jīng)檢查過(guò) ， 而標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行