【文章內(nèi)容簡介】 V3 V4 V5 V6 V7 V8 ① P=0 T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ T=+∞ ② P=T=3 T=+∞ T=7 T=+∞ T=+∞ T=+∞ T=+∞ ③ T=6 T=7 P=T=5 T=+∞ T=+∞ T=+∞ ④ P=T=6 T=6 T=8 T=+∞ T=+∞ ⑤ P=T=6 T=8 T=9 T=12 ⑥ P=T=8 T=10 T=10 ⑦ P=T=9 T=11 再無其它 T 標號 ， 所以 T(V8)=P(V8)=10。 min L(μ)=10 ⑧ P=T=10 由此看到，此方法不僅求出了從 V1 到 V8 的最短路長，同時也求出了從 V1 到 任意一點 的最短路長。將從V1 到 任一點的最短路權(quán)標在圖上，即可求出從 V1 到 任一點的最短路線。本例中 V1 到 V8 的最短路線是： v1 → v 2 → v 5→ v 6 → v 8 1v 2v3v4v5v 9v8v7v6v6 2 3 1 2 1 6 4 10 3 6 2 3 4 2 10 1v3v2v5v8v（ 二 ） 、 逐次逼近法 算法的基本思路與步驟： 首先設任一點 vi到任一點 vj都有一條弧 。 顯然 ， 從 v1到 vj的最短路是從 v1出發(fā) ， 沿著這條路到某個點 vi再沿弧 (vi,vj)到 vj。 則 v1到 vi的這條路必然也是 v1到 vi的所有路中的最短路 。 設 P1j表示從 v1到 vj的最短路長 ， P1i表示從 v1到vi的最短路長 ， 則有下列方程： 開始時 ， 令 即用 v1到 vj的直接距離做初始解 。 從第二步起 ， 使用遞推公式： 求 ， 當進行到第 t步 ， 若出現(xiàn) 則停止計算， 即為 v1到各點的最短路長。 }{min 11 jiiij lPP ?? ),2,1(1)1(1 njlP jj ??? ）（ nklPjikiikj ,3,2][min )1(1)(1 ???? ?)(1kjP ）（ njPP tjtj ,2,1)1(1)(1 ??? ? ）（ njP tj ,2,1)(1 ??例二、 － 1 8 v1 v2 v3 v4 v5 － 2 6 － 3 － 5 － 1 － 3 － 5 2 1 － 1 2 1 1 v6 v7 v8 3 7 v1 v2 v3 v4 v5 v6 v7 v8 P(1) P(2) P(3) P(4) v1 0 1 2 3 0 0 0 0 v2 6 0 2 1 5 5 5 v3 3 0 5 1 2 2 2 2 v4 8 0 2 3 7 7 7 v5 1 0 1 3 3 v6 1 0 1 7 1 1 1 v7 1 0 5 5 5 v8 3 5 0 6 6 求圖中 v1到 各點的最短路 － 1 8 v1 v2 v3 v4 v5 － 2 6 － 3 － 5 － 1 － 3 － 5 2 1 － 1 2 1 1 v6 v7 v8 3 7 （ 0， 0） （ v3 ， 5） （ v1 ， 2） （ v3 ， 7） （ v2 ， 3） （ v4 ， 5） （ v3 ， 1） （ v6 ， 6） 例三、求： 5年內(nèi)，哪些年初購置新設備，使 5年內(nèi)的總費用最小。 解： （ 1） 分析：可行的購置方案 （ 更新計劃 ） 是很多的 ， 如： 1） 每年購置一臺新的 ， 則對應的費用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購置新的 ， 一直用到第五年年底 ， 則總費用為： 11+5+6+8+11+18 = 59 顯然不同的方案對應不同的費用。 第 i年度 1 2 3 4 5 購置費 11 11 12 12 13 設備役齡 01 12 23 34 45 維修費用 5 6 8 11 18 （ 2） 方法：將此問題用一個賦權(quán)有向圖來描述 ， 然后求這個賦權(quán)有向圖的最短路 。 求解步驟： 1） 畫賦權(quán)有向圖： 設 Vi 表示第 i年初 ， (Vi ,Vj )表示第 i 年初購買新設備用到第 j年初 （ j1年底 ） ， 而 Wi j 表示相應費用 ，則 5年的一個更新計劃相當于從 V1 到 V6的一條路 。 2）求解 （標號法） W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6++8+11+18=59 W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18 W34 =12+5=17 W35 =12+5+6=23 W36 =12+5+6+8=31 例四、 某工廠使用一種設備，這種設備在一定的年限內(nèi)隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設備是否更新。若購置設備，每年需支付購置費用；若繼續(xù)使用舊設備，需要支付維修與運行費用，而且隨著設備的老化會逐年增加。計劃期（五年）內(nèi)中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內(nèi)的總費用最小。 年份 1 2 3 4 5 購置費 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費 5 7 12 18 25 年份 1 2 3 4 5 購置費 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費 5 7 12 18 25 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 30 四、 最大流問題 （ 一 ） 、 基本概念 設一個賦權(quán)有向圖 D=（ V, E） ,在 V中指定一個發(fā)點vs和一個收點 vt ,其它的點叫做中間點 。 對于 D中的每一個弧 （ vi , vj） ∈ E ,都有一個非負數(shù) cij,叫做弧的容量 。 我們把這樣的圖 D叫做一個容量網(wǎng)絡 ， 簡稱網(wǎng)絡 ， 記做 D=（ V， E， C） 。 網(wǎng)絡 D上的流，是指定義在弧集合 E上的一個函數(shù) 其中 f(vi ,vj) =fij 叫做弧 (vi， vj)上的流量。 ? ? }{),( jiji fvvff ??稱滿足下列條件的流為可行流： （ 1）容量條件：對于每一個弧（ vi ,vj） ∈ E 有 0 ? fij ? cij 。 （ 2） 平衡條件： 對于發(fā)點 vs， 有 對于收點 vt ， 有 對于中間點，有 ? ?? ???Evv Evvsjjsjs sjWff),( ),( ?? ? ???Evv Evv tjjtjt tj Wff),( ),(? ?? ? ??Evv Evv ijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 fij＞ 0 的弧為非零流弧，fij＝ 0 的弧叫做零流弧。 2v1v 3v 4v 5v6v 7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 圖中 為零流弧，其余為非飽和弧。 ) , ( 63 vv 容量網(wǎng)絡 G， 若 為網(wǎng)絡中從 vs到 vt的一條鏈 ， 給 定向為從 vs到 vt， 上的弧凡與 方向相同的稱為前向弧 ， 凡與 方向相反的稱為后向弧 ， 其集合分別用 和 表示 。 f 是一個可行流 ， 如果滿足： 則