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