圖與網(wǎng)絡(luò)分析物流運(yùn)籌學(xué)課件

圖與網(wǎng)絡(luò)分析在物流系統(tǒng)中的應(yīng)用(GraphTheoryandNetworkAnalysis)圖與網(wǎng)絡(luò)的基本知識(shí)最短路問(wèn)題樹(shù)及最小樹(shù)問(wèn)題圖與網(wǎng)絡(luò)分析在物流系統(tǒng)中的應(yīng)用圖與網(wǎng)絡(luò)的基本知識(shí)最短路問(wèn)題BDACABCD哥尼斯堡七空橋一筆畫問(wèn)題BDACABCD哥尼斯堡七空橋一筆畫問(wèn)題應(yīng)用及解決的問(wèn)題配送運(yùn)輸規(guī)劃問(wèn)題物流車輛規(guī)劃調(diào)度系統(tǒng)物流園區(qū)規(guī)劃應(yīng)用及解決的問(wèn)題配送運(yùn)輸規(guī)劃問(wèn)題一、

圖與網(wǎng)絡(luò)的基本知識(shí)（一）、圖與網(wǎng)絡(luò)的基本概念

EADCB1、一個(gè)圖是由點(diǎn)和連線組成。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊）一、圖與網(wǎng)絡(luò)的基本知識(shí)EADCB1、一個(gè)圖是由一個(gè)圖是由點(diǎn)集和中元素的無(wú)序?qū)Φ囊粋€(gè)集合構(gòu)成的二元組，記為G=(V，E)，其中V中的元素叫做頂點(diǎn)，V表示圖G

的點(diǎn)集合；E

中的元素叫做邊，E表示圖G

的邊集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例圖1一個(gè)圖是由點(diǎn)集和中元素的無(wú)序?qū)?、如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無(wú)向圖，記作G=(V，E)，連接點(diǎn)的邊記作[vi,vj]，或者[vj,vi]。3、如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V,A)，其中V表示有向圖D的點(diǎn)集合，A表示有向圖D的弧集合。一條方向從vi指向vj

的弧，記作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}圖22、如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無(wú)向圖，記作4、一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)。5、如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀?、一個(gè)無(wú)環(huán)，無(wú)多重邊的圖稱為簡(jiǎn)單圖，一個(gè)無(wú)環(huán)，有多重邊的圖稱為多重圖。7、每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖稱為完全圖。有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡(jiǎn)單圖。4、一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)。6、v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度為零的點(diǎn)稱為弧立點(diǎn)，度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。8、以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的度（次），記作。圖中

d(v1)=4，d(v6)=4（環(huán)計(jì)兩度）v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9定理1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。定理2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。有向圖中，以

vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用表示；以

vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用表示；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次。定理1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。9、設(shè)G1=（V1,E1），G2=（V2,E2）如果V2

V1,E2E1

稱G2

是G1

的子圖；如果V2=V1,E2E1

稱G2

是G1

的部分圖或支撐子圖。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖9、設(shè)G1=（V1,E1），G2=（V2在實(shí)際應(yīng)用中，給定一個(gè)圖G=（V，E）或有向圖D=（V，A），在V中指定兩個(gè)點(diǎn)，一個(gè)稱為始點(diǎn)（或發(fā)點(diǎn)），記作v1，一個(gè)稱為終點(diǎn)（或收點(diǎn)），記作vn，其余的點(diǎn)稱為中間點(diǎn)。對(duì)每一條弧，對(duì)應(yīng)一個(gè)數(shù)，稱為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。10、由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。如:v0，e1，v1，e2，v2，e3，v3,…,vn-1,en

，vn，記作（v0，v1，v2，v3,…,vn-1，vn），

在實(shí)際應(yīng)用中，給定一個(gè)圖G=（V，E）或有向圖De3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1011、圖中任意兩點(diǎn)之間均至少有一條通路，則稱此圖為連通圖，否則稱為不連通圖。其鏈長(zhǎng)為n

，其中v0，vn分別稱為鏈的起點(diǎn)和終點(diǎn)。若鏈中所含的邊均不相同，則稱此鏈為簡(jiǎn)單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈,也稱通路。e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9（二）、圖的矩陣表示對(duì)于網(wǎng)絡(luò)（賦權(quán)圖）G=（V，E），其中邊有權(quán)，構(gòu)造矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)為n，構(gòu)造一個(gè)矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。（二）、圖的矩陣表示設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)例權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437例權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v6433225問(wèn)題圖（頂點(diǎn)、邊）、有限圖、無(wú)限圖無(wú)向圖、有向圖、環(huán)、多重邊多重圖、簡(jiǎn)單圖、完全圖、有向完全圖、二部圖頂點(diǎn)的次、出次、入次、懸掛點(diǎn)、孤立點(diǎn)、奇點(diǎn)、偶點(diǎn)子圖、生成子圖（支撐圖）、網(wǎng)絡(luò)（賦權(quán)圖）鏈、初等鏈、圈、初等圈、回路、連通圖圖的矩陣表示、鄰接矩陣歐拉道路、歐拉回路、中國(guó)郵路問(wèn)題問(wèn)題圖（頂點(diǎn)、邊）、有限圖、無(wú)限圖樹(shù)的概念樹(shù)、樹(shù)葉、分枝點(diǎn)數(shù)的性質(zhì)生成子圖、生成樹(shù)、樹(shù)枝、弦最小生成樹(shù)避圈法、破圈法有向樹(shù)、根樹(shù)、葉、分枝點(diǎn)、叉樹(shù)樹(shù)的概念樹(shù)、樹(shù)葉、分枝點(diǎn)

二、樹(shù)及最小樹(shù)問(wèn)題

已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。v1v2v3v4v5v61、一個(gè)連通的無(wú)圈的無(wú)向圖叫做樹(shù)。樹(shù)中次為1的點(diǎn)稱為樹(shù)葉，次大于1的點(diǎn)稱為分支點(diǎn)。二、樹(shù)及最小樹(shù)問(wèn)題v1v2v3v4v5v61、一樹(shù)

的性質(zhì)：（1）樹(shù)必連通，但無(wú)回路（圈）。（2）n個(gè)頂點(diǎn)的樹(shù)必有n-1條邊。（3）樹(shù)

中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。（4）樹(shù)

連通，但去掉任一條邊，必變?yōu)椴贿B通。（5）樹(shù)無(wú)回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。v1v2v3v4v5v6樹(shù)的性質(zhì)：v1v2v3v4v5v62、設(shè)圖是圖G=(V,E)的一支撐子圖，如果圖是一個(gè)樹(shù),那么稱K是G的一個(gè)生成樹(shù)（支撐樹(shù)），或簡(jiǎn)稱為圖G的樹(shù)。圖G中屬于生成樹(shù)的邊稱為樹(shù)枝，不在生成樹(shù)中的邊稱為弦。一個(gè)圖G有生成樹(shù)的充要條件是G

是連通圖。v1v2v3v4v5v1v2v3v4v52、設(shè)圖是圖G=(V,E用避圈法求出下圖的一個(gè)生成樹(shù)。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8用避圈法求出下圖的一個(gè)生成樹(shù)。v1v2v3v4v5e1e2（一）破圈法（一）破圈法（二）避圈法

在圖中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，再找一條與{e1，e2}不構(gòu)成圈的邊e3。一般設(shè)已有{e1，e2，…，ek}，找一條與{e1，e2，…，ek}中任何一些邊不構(gòu)成圈的邊ek+1，重復(fù)這個(gè)過(guò)程，直到不能進(jìn)行為止。（二）避圈法在圖中任取一條邊e1，找一條與e1v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5v1v2v3v4v5v6v1v3v1v3v2v1v3v2v53、最小生成樹(shù)問(wèn)題

如果圖是圖G的一個(gè)生成樹(shù)，那么稱E1上所有邊的權(quán)的和為生成樹(shù)T的權(quán)，記作S(T)。如果圖G的生成樹(shù)T*的權(quán)S(T*)，在G的所有生成樹(shù)T中的權(quán)最小，即那么稱T*是G的最小生成樹(shù)。某六個(gè)城市之間的道路網(wǎng)如圖

所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使電話線的總長(zhǎng)度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v6123443、最小生成樹(shù)問(wèn)題如果圖是圖G的一v1v2v3v4v514231352v1v2v3v4v514231352

最短路的一般提法為：設(shè)為連通圖，圖中各邊有權(quán)（表示之間沒(méi)有邊），為圖中任意兩點(diǎn)，求一條路，使它為從到的所有路中總權(quán)最短。即：最小。(一)、狄克斯屈拉(Dijkstra)算法適用于wij≥0，給出了從vs到任意一個(gè)點(diǎn)vj的最短路。三、最短路問(wèn)題(一)、狄克斯屈拉(Dijk算法步驟：1.給始點(diǎn)vs以P標(biāo)號(hào)，這表示從vs到

vs的最短距離為0，其余節(jié)點(diǎn)均給T標(biāo)號(hào)，。2.設(shè)節(jié)點(diǎn)vi

為剛得到P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)vj，其中，且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改：3.比較所有具有T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為P標(biāo)號(hào)，即：

當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部節(jié)點(diǎn)均為P標(biāo)號(hào)，則停止，否則用vk代替vi，返回步驟（2）。算法步驟：例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421

解（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。（2）（3）（4）例一、用Dijkstra算法求下圖從v1到v6的v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追蹤得v1到v6的最短路為：v1v2v3v4v6v5352242421（5）（6）（7）237184566134105275934682求從1到8的最短路徑237184566134105275934682求從1到8的237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1},237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,4237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路徑為{1，4，7，5，8}，長(zhǎng)度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2求從V1

到V8

的最短路線。求從V1到V8的最短路線。V1V2V3V4V5V6V7V8①P=0T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞②P=T=3T=+∞T=7T=+∞T=+∞T=+∞T=+∞

③T=6T=7P=T=5T=+∞T=+∞T=+∞

④P=T=6T=6

T=8T=+∞T=+∞

⑤P=T=6

T=8T=9T=12

⑥P=T=8T=10T=10

⑦P=T=9T=11再無(wú)其它T標(biāo)號(hào)，所以

T(V8)=P(V8)=10;minL(μ)=10⑧P=T=10V1V2V3V4V5V6V7V8①P=0T=+∞T=+∞T由此看到，此方法不僅求出了從V1

到V8

的最短路長(zhǎng)，同時(shí)也求出了從V1

到任意一點(diǎn)的最短路長(zhǎng)。將從V1

到任一點(diǎn)的最短路權(quán)標(biāo)在圖上，即可求出從V1

到任一點(diǎn)的最短路線。本例中V1

到V8

的最短路線是：

v1→v2→v5→v6→v8

由此看到，此方法不僅求出了從V1到V8623121641036234210623121641036234210（二）、逐次逼近法算法的基本思路與步驟：首先設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個(gè)點(diǎn)vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長(zhǎng)，P1i表示從v1到vi的最短路長(zhǎng)，則有下列方程：開(kāi)始時(shí)，令即用v1到vj的直接距離做初始解。從第二步起，使用遞推公式：求，當(dāng)進(jìn)行到第t步，若出現(xiàn)則停止計(jì)算，即為v1到各點(diǎn)的最短路長(zhǎng)。（二）、逐次逼近法例二、

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66求圖中v1到各點(diǎn)的最短路例二、

－18v1v2v3v4v5－26－3－5－1－3－5

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）

－18v1v2v3v4v5－26－3－5－1－3－521－例三、求：5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。解：（1）分析：可行的購(gòu)置方案（更新計(jì)劃）是很多的，如：1）每年購(gòu)置一臺(tái)新的，則對(duì)應(yīng)的費(fèi)用為：

11+11+12+12+13+5+5+5+5+5=842)第一年購(gòu)置新的，一直用到第五年年底，則總費(fèi)用為：11+5+6+8+11+18=59

顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。第i年度

12345購(gòu)置費(fèi)1111121213設(shè)備役齡0-11-22-33-44-5維修費(fèi)用

5681118例三、求：5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。（2）方法：將此問(wèn)題用一個(gè)賦權(quán)有向圖來(lái)描述，然后求這個(gè)賦權(quán)有向圖的最短路。求解步驟：1）畫賦權(quán)有向圖：設(shè)Vi

表示第i年初，(Vi,Vj)表示第i年初購(gòu)買新設(shè)備用到第j年初（j-1年底），而Wij

表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從V1

到V6的一條路。2）求解（標(biāo)號(hào)法）（2）方法：將此問(wèn)題用一個(gè)賦權(quán)有向圖來(lái)描述，然后求這個(gè)賦權(quán)W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31W12=11+5=16W23=11+5=16例四、某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時(shí)間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購(gòu)置設(shè)備，每年需支付購(gòu)置費(fèi)用；若繼續(xù)使用舊設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化會(huì)逐年增加。計(jì)劃期（五年）內(nèi)中每年的購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表所示，工廠要制定今后五年設(shè)備更新計(jì)劃，問(wèn)采用何種方案才能使包括購(gòu)置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。年份12345購(gòu)置費(fèi)1820212324使用年數(shù)0~11~22~33~44~5維修費(fèi)57121825例四、某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著年份12345購(gòu)置費(fèi)1820212324使用年數(shù)0~11~22~33~44~5維修費(fèi)5712182528v1v2v3v4v5v62325262930426085324462334530年份12345購(gòu)置費(fèi)1820212324使用年數(shù)0~11~2四、最大流問(wèn)題（一）、基本概念1、設(shè)一個(gè)賦權(quán)有向圖D=（V,E）,在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt

,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)弧（vi

,vj）∈E,都有一個(gè)非負(fù)數(shù)cij,叫做弧的容量。我們把這樣的圖D叫做一個(gè)容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)，記做D=（V，E，C）。網(wǎng)絡(luò)D上的流，是指定義在弧集合E上的一個(gè)函數(shù)其中f(vi

,vj)=fij

叫做弧(vi，vj)上的流量。

四、最大流問(wèn)題2、稱滿足下列條件的流為可行流：（1）容量條件：對(duì)于每一個(gè)?。╲i,vj）∈E 有 0≤

fij

≤

cij

。（2）平衡條件：對(duì)于發(fā)點(diǎn)vs，有對(duì)于收點(diǎn)vt

，有對(duì)于中間點(diǎn)，有可行流中fij＝cij

的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0的弧為非零流弧，fij＝0的弧叫做零流弧。2、稱滿足下列條件的流為可行流：可行流中fij＝cij的13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)圖中為零流弧，其余為非飽和弧。13(5)9(3)4(1)5(3)6(3)5(23、容量網(wǎng)絡(luò)G，若為網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向?yàn)閺膙s到vt，上的弧凡與方向相同的稱為前向弧，凡與方向相反的稱為后向弧，其集合分別用和表示。f

是一個(gè)可行流，如果滿足：

則稱為從vs到vt

的關(guān)于f的一條增廣鏈。推論可行流f是最大流的充分必要條件是不存在從vs到vt

的關(guān)于f的一條可增廣鏈。即中的每一條弧都是非飽和弧即中的每一條弧都是非零流弧推論可行流f是最大流的充分必要條件是不存在從vs到v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一個(gè)增廣鏈顯然圖中增廣鏈不止一條13(5)9(3)4(1)5(3)6(3)5(24、容量網(wǎng)絡(luò)G=（V，E，C），vs為始點(diǎn)，vt為終點(diǎn)。如果把V分成兩個(gè)非空集合使，則所有始點(diǎn)屬于S，而終點(diǎn)屬于的弧的集合，稱為由S決定的截集,記作。截集中所有弧的容量之和，稱為這個(gè)截集的容量，記為。vsv1v2v4v3vt374556378S4、容量網(wǎng)絡(luò)G=（V，E，C），vs為始點(diǎn)，vt13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)，則截集為容量為2413(5)9(3)4(1)5(3)6(3)5(213(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)設(shè)，則截集為容量為2013(5)9(3)4(1)5(3)6(3)5(2（二）求最大流的標(biāo)號(hào)法標(biāo)號(hào)過(guò)程：1．

給發(fā)點(diǎn)vs

標(biāo)號(hào)（0，+∞）。2．

取一個(gè)已標(biāo)號(hào)的點(diǎn)vi，對(duì)于vi一切未標(biāo)號(hào)的鄰接點(diǎn)vj

按下列規(guī)則處理：（1）如果邊，且，那么給vj

標(biāo)號(hào)，其中：（2）如果邊，且，那么給vj

標(biāo)號(hào)，其中：3．重復(fù)步驟2，直到vt被標(biāo)號(hào)或標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，則標(biāo)號(hào)結(jié)束。若vt被標(biāo)號(hào)，則存在一條增廣鏈，轉(zhuǎn)調(diào)整過(guò)程；若vt未被標(biāo)號(hào)，而標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，這時(shí)的可行流就是最大流。（二）求最大流的標(biāo)號(hào)法調(diào)整過(guò)程設(shè)1．令2．去掉所有標(biāo)號(hào)，回到第一步，對(duì)可行流重新標(biāo)號(hào)。調(diào)整過(guò)程求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)（0，+∞）（-v1,1）（+vs,4）（-v2，1）（+v2，1）(+v3，1)求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為(1,(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)(1,0)v2v1v4v3vsvt(3,3)(5,2)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)（0，+∞）（+vs,3）最小截集(1,0)v2v1v4v3vsvt(3,3)(5,13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)13(5)9(3)4(1)5(3)6(3)5(213(11)9(9)4(0)5(5)6(6)5(5)5(4)5(4)4(4)4(3)9(9)10(7)截集1截集2最小截量為：9+6+5=2013(11)9(9)4(0)5(5)6(6)5(70（70）70（50）130（100）150（130）150（150）50（20）50（50）120（30）100（100）∞（120）∞（230）∞（150）∞（200）70（70）70（50）130（100）150（130）15第五節(jié)最小費(fèi)用最大流問(wèn)題定義8.17已知網(wǎng)絡(luò)G=（V，E，C，d），f是G上的一個(gè)可行流，為一條從vs到vt的增廣鏈，稱為鏈的費(fèi)用。

若*是從vs到vt的增廣鏈中費(fèi)用最小的增廣鏈，則稱*是最小費(fèi)用增廣鏈。結(jié)論：如果可行流f在流量為W(f)的所有可行流中的費(fèi)用最小，并且*是關(guān)于f的所有增廣鏈中的費(fèi)用最小的增廣鏈，那么沿增廣鏈*調(diào)整可行流f，得到的新可行流f*也是流量為W(f*)的所有可行流中的最小費(fèi)用流。當(dāng)f*

是最大流時(shí)，就是最小費(fèi)用最大流。第五節(jié)最小費(fèi)用最大流問(wèn)題定義8.17已知網(wǎng)絡(luò)G=（V尋找關(guān)于f的最小費(fèi)用增廣鏈：構(gòu)造一個(gè)關(guān)于f的賦權(quán)有向圖L(f)，其頂點(diǎn)是原網(wǎng)絡(luò)G的頂點(diǎn)，而將G中的每一條弧(vi,vj

)變成兩個(gè)相反方向的弧（vi，vj）和(vj

,vi)，并且定義圖中弧的權(quán)l(xiāng)ij為：1.當(dāng)，令

2.當(dāng)（vj，vi）為原來(lái)網(wǎng)絡(luò)G中（vi，vj）的反向弧，令在網(wǎng)絡(luò)G中尋找關(guān)于f的最小費(fèi)用增廣鏈等價(jià)于在L(f)中尋求從vs

到vt

的最短路。尋找關(guān)于f的最小費(fèi)用增廣鏈：步驟：（1）取零流為初始可行流，f(0)={0}。（2）一般地，如果在第k-1步得到最小費(fèi)用流f(k-1)，則構(gòu)造圖L(f(k-1)

)。（3）在L(f(k-1)

)中，尋求從vs到vt的最短路。若不存在最短路，則f(k-1)就是最小費(fèi)用最大流；否則轉(zhuǎn)(4)。（4）如果存在最短路，則在可行流f

(k－1)的圖中得到與此最短路相對(duì)應(yīng)的增廣鏈，在增廣鏈上，對(duì)f

(k－1)進(jìn)行調(diào)整，調(diào)整量為：步驟：令得到新可行流f

(k)。對(duì)f

(k)重復(fù)上面步驟，返回（2）。例8.11求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)是（bij,cij）(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)令得到新可行流f(k)。對(duì)f(k)重復(fù)上面步驟，返回（3vsv2v1vtv3164122(1)L(f(0))(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)0vsv2v1vtv3300333(2)f(1)1=3W(f(1))=3－1(3)L(f(1))－23vsv2v1vtv316412－1－23vsv2v1vtv3164122(1)L(f1vsv2v1vtv3400343(4

)f(2)2=1W(f(2))=4(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)(5)L(f(2))－3vsv2v1vtv3－1412－2－23－1661vsv2v1vtv3401453(6

)f(3)3=1W(f(3))=51vsv2v1vtv3400343(4)f(2)(7)L(f(3))vsv2v1vtv3－3－141-2－23－161vsv2v1vtv3434450(8

)f(4)4=3W(f(4))=80vsv2v1vtv34455505=1W(f(5))=9(10

)f(5)－1-23－1vsv2v1vtv3－34126(9)L(f(4))-4-6(7)L(f(3))vsv2v1vtv3－3－143－12－14(11)L(f(5))126－4vsv2v1vtv3－63－12－14(11)L(f(5))126－第六節(jié)中國(guó)郵遞員問(wèn)題

一、歐拉回路與道路定義8.18連通圖G中，若存在一條道路，經(jīng)過(guò)每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過(guò)每邊一次且僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖。定理8.7一個(gè)多重連通圖G是歐拉圖的充分必要條件是G中無(wú)奇點(diǎn)。推論一個(gè)多重連通圖G有歐拉道路的充分必要條件是G有且僅有兩個(gè)奇點(diǎn)。第六節(jié)中國(guó)郵遞員問(wèn)題一、歐拉回路與道路ABCDABCD二、奇偶點(diǎn)圖上作業(yè)法（1）找出圖G中的所有的奇頂點(diǎn)，把它們兩兩配成對(duì)，而每對(duì)奇點(diǎn)之間必有一條通路，把這條通路上的所有邊作為重復(fù)邊追加到圖中去，這樣得到的新連通圖必?zé)o奇點(diǎn)。（2）如果邊e=（u,v）上的重復(fù)邊多于一條，則可從重復(fù)邊中去掉偶數(shù)條，使得其重復(fù)邊至多為一條，圖中的頂點(diǎn)仍全部都是偶頂點(diǎn)。（3）檢查圖中的每一個(gè)圈，如果每一個(gè)圈的重復(fù)邊的總長(zhǎng)不大于該圈總長(zhǎng)的一半，則已經(jīng)求得最優(yōu)方案。如果存在一個(gè)圈，重復(fù)邊的總長(zhǎng)大于該圈總長(zhǎng)的一半時(shí)，則將這個(gè)圈中的重復(fù)邊去掉，再將該圈中原來(lái)沒(méi)有重復(fù)邊的各邊加上重復(fù)邊，其它各圈的邊不變，返回步驟（2）。二、奇偶點(diǎn)圖上作業(yè)法判定標(biāo)準(zhǔn)1:在最優(yōu)郵遞路線上，圖中的每一條邊至多有一條重復(fù)邊。判定標(biāo)準(zhǔn)2:

在最優(yōu)郵遞路線上，圖中每一個(gè)圈的重復(fù)邊總權(quán)小于或等于該圈總權(quán)的一半。例8.12求解下圖所示網(wǎng)絡(luò)的中國(guó)郵路問(wèn)題，圖中數(shù)字為該邊的長(zhǎng)。v1v2v3v4v5v6v7v8v9243449556434判定標(biāo)準(zhǔn)1:在最優(yōu)郵遞路線上，圖中的每一條邊至多有一條重復(fù)v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449643455l12+2l23+2l36+2l89+2l78+l69+l14+2l47=51v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449556434圖與網(wǎng)絡(luò)分析在物流系統(tǒng)中的應(yīng)用(GraphTheoryandNetworkAnalysis)圖與網(wǎng)絡(luò)的基本知識(shí)最短路問(wèn)題樹(shù)及最小樹(shù)問(wèn)題圖與網(wǎng)絡(luò)分析在物流系統(tǒng)中的應(yīng)用圖與網(wǎng)絡(luò)的基本知識(shí)最短路問(wèn)題BDACABCD哥尼斯堡七空橋一筆畫問(wèn)題BDACABCD哥尼斯堡七空橋一筆畫問(wèn)題應(yīng)用及解決的問(wèn)題配送運(yùn)輸規(guī)劃問(wèn)題物流車輛規(guī)劃調(diào)度系統(tǒng)物流園區(qū)規(guī)劃應(yīng)用及解決的問(wèn)題配送運(yùn)輸規(guī)劃問(wèn)題一、

圖與網(wǎng)絡(luò)的基本知識(shí)（一）、圖與網(wǎng)絡(luò)的基本概念

EADCB1、一個(gè)圖是由點(diǎn)和連線組成。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊）一、圖與網(wǎng)絡(luò)的基本知識(shí)EADCB1、一個(gè)圖是由一個(gè)圖是由點(diǎn)集和中元素的無(wú)序?qū)Φ囊粋€(gè)集合構(gòu)成的二元組，記為G=(V，E)，其中V中的元素叫做頂點(diǎn)，V表示圖G

的點(diǎn)集合；E

中的元素叫做邊，E表示圖G

的邊集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例圖1一個(gè)圖是由點(diǎn)集和中元素的無(wú)序?qū)?、如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無(wú)向圖，記作G=(V，E)，連接點(diǎn)的邊記作[vi,vj]，或者[vj,vi]。3、如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V,A)，其中V表示有向圖D的點(diǎn)集合，A表示有向圖D的弧集合。一條方向從vi指向vj

的弧，記作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}圖22、如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無(wú)向圖，記作4、一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)。5、如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀?、一個(gè)無(wú)環(huán)，無(wú)多重邊的圖稱為簡(jiǎn)單圖，一個(gè)無(wú)環(huán)，有多重邊的圖稱為多重圖。7、每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖稱為完全圖。有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡(jiǎn)單圖。4、一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)。6、v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度為零的點(diǎn)稱為弧立點(diǎn)，度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。8、以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的度（次），記作。圖中

d(v1)=4，d(v6)=4（環(huán)計(jì)兩度）v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9定理1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。定理2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。有向圖中，以

vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用表示；以

vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用表示；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次。定理1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。9、設(shè)G1=（V1,E1），G2=（V2,E2）如果V2

V1,E2E1

稱G2

是G1

的子圖；如果V2=V1,E2E1

稱G2

是G1

的部分圖或支撐子圖。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖9、設(shè)G1=（V1,E1），G2=（V2在實(shí)際應(yīng)用中，給定一個(gè)圖G=（V，E）或有向圖D=（V，A），在V中指定兩個(gè)點(diǎn)，一個(gè)稱為始點(diǎn)（或發(fā)點(diǎn)），記作v1，一個(gè)稱為終點(diǎn)（或收點(diǎn)），記作vn，其余的點(diǎn)稱為中間點(diǎn)。對(duì)每一條弧，對(duì)應(yīng)一個(gè)數(shù)，稱為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。10、由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。如:v0，e1，v1，e2，v2，e3，v3,…,vn-1,en

，vn，記作（v0，v1，v2，v3,…,vn-1，vn），

在實(shí)際應(yīng)用中，給定一個(gè)圖G=（V，E）或有向圖De3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1011、圖中任意兩點(diǎn)之間均至少有一條通路，則稱此圖為連通圖，否則稱為不連通圖。其鏈長(zhǎng)為n

，其中v0，vn分別稱為鏈的起點(diǎn)和終點(diǎn)。若鏈中所含的邊均不相同，則稱此鏈為簡(jiǎn)單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈,也稱通路。e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9（二）、圖的矩陣表示對(duì)于網(wǎng)絡(luò)（賦權(quán)圖）G=（V，E），其中邊有權(quán)，構(gòu)造矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)為n，構(gòu)造一個(gè)矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。（二）、圖的矩陣表示設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)例權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437例權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v6433225問(wèn)題圖（頂點(diǎn)、邊）、有限圖、無(wú)限圖無(wú)向圖、有向圖、環(huán)、多重邊多重圖、簡(jiǎn)單圖、完全圖、有向完全圖、二部圖頂點(diǎn)的次、出次、入次、懸掛點(diǎn)、孤立點(diǎn)、奇點(diǎn)、偶點(diǎn)子圖、生成子圖（支撐圖）、網(wǎng)絡(luò)（賦權(quán)圖）鏈、初等鏈、圈、初等圈、回路、連通圖圖的矩陣表示、鄰接矩陣歐拉道路、歐拉回路、中國(guó)郵路問(wèn)題問(wèn)題圖（頂點(diǎn)、邊）、有限圖、無(wú)限圖樹(shù)的概念樹(shù)、樹(shù)葉、分枝點(diǎn)數(shù)的性質(zhì)生成子圖、生成樹(shù)、樹(shù)枝、弦最小生成樹(shù)避圈法、破圈法有向樹(shù)、根樹(shù)、葉、分枝點(diǎn)、叉樹(shù)樹(shù)的概念樹(shù)、樹(shù)葉、分枝點(diǎn)

二、樹(shù)及最小樹(shù)問(wèn)題

已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。v1v2v3v4v5v61、一個(gè)連通的無(wú)圈的無(wú)向圖叫做樹(shù)。樹(shù)中次為1的點(diǎn)稱為樹(shù)葉，次大于1的點(diǎn)稱為分支點(diǎn)。二、樹(shù)及最小樹(shù)問(wèn)題v1v2v3v4v5v61、一樹(shù)

的性質(zhì)：（1）樹(shù)必連通，但無(wú)回路（圈）。（2）n個(gè)頂點(diǎn)的樹(shù)必有n-1條邊。（3）樹(shù)

中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。（4）樹(shù)

連通，但去掉任一條邊，必變?yōu)椴贿B通。（5）樹(shù)無(wú)回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。v1v2v3v4v5v6樹(shù)的性質(zhì)：v1v2v3v4v5v62、設(shè)圖是圖G=(V,E)的一支撐子圖，如果圖是一個(gè)樹(shù),那么稱K是G的一個(gè)生成樹(shù)（支撐樹(shù)），或簡(jiǎn)稱為圖G的樹(shù)。圖G中屬于生成樹(shù)的邊稱為樹(shù)枝，不在生成樹(shù)中的邊稱為弦。一個(gè)圖G有生成樹(shù)的充要條件是G

是連通圖。v1v2v3v4v5v1v2v3v4v52、設(shè)圖是圖G=(V,E用避圈法求出下圖的一個(gè)生成樹(shù)。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8用避圈法求出下圖的一個(gè)生成樹(shù)。v1v2v3v4v5e1e2（一）破圈法（一）破圈法（二）避圈法

在圖中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，再找一條與{e1，e2}不構(gòu)成圈的邊e3。一般設(shè)已有{e1，e2，…，ek}，找一條與{e1，e2，…，ek}中任何一些邊不構(gòu)成圈的邊ek+1，重復(fù)這個(gè)過(guò)程，直到不能進(jìn)行為止。（二）避圈法在圖中任取一條邊e1，找一條與e1v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5v1v2v3v4v5v6v1v3v1v3v2v1v3v2v53、最小生成樹(shù)問(wèn)題

如果圖是圖G的一個(gè)生成樹(shù)，那么稱E1上所有邊的權(quán)的和為生成樹(shù)T的權(quán)，記作S(T)。如果圖G的生成樹(shù)T*的權(quán)S(T*)，在G的所有生成樹(shù)T中的權(quán)最小，即那么稱T*是G的最小生成樹(shù)。某六個(gè)城市之間的道路網(wǎng)如圖

所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使電話線的總長(zhǎng)度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v6123443、最小生成樹(shù)問(wèn)題如果圖是圖G的一v1v2v3v4v514231352v1v2v3v4v514231352

最短路的一般提法為：設(shè)為連通圖，圖中各邊有權(quán)（表示之間沒(méi)有邊），為圖中任意兩點(diǎn)，求一條路，使它為從到的所有路中總權(quán)最短。即：最小。(一)、狄克斯屈拉(Dijkstra)算法適用于wij≥0，給出了從vs到任意一個(gè)點(diǎn)vj的最短路。三、最短路問(wèn)題(一)、狄克斯屈拉(Dijk算法步驟：1.給始點(diǎn)vs以P標(biāo)號(hào)，這表示從vs到

vs的最短距離為0，其余節(jié)點(diǎn)均給T標(biāo)號(hào)，。2.設(shè)節(jié)點(diǎn)vi

為剛得到P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)vj，其中，且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改：3.比較所有具有T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為P標(biāo)號(hào)，即：

當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部節(jié)點(diǎn)均為P標(biāo)號(hào)，則停止，否則用vk代替vi，返回步驟（2）。算法步驟：例一、用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421

解（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。（2）（3）（4）例一、用Dijkstra算法求下圖從v1到v6的v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追蹤得v1到v6的最短路為：v1v2v3v4v6v5352242421（5）（6）（7）237184566134105275934682求從1到8的最短路徑237184566134105275934682求從1到8的237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1},237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,4237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路徑為{1，4，7，5，8}，長(zhǎng)度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2求從V1

到V8

的最短路線。求從V1到V8的最短路線。V1V2V3V4V5V6V7V8①P=0T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞②P=T=3T=+∞T=7T=+∞T=+∞T=+∞T=+∞

③T=6T=7P=T=5T=+∞T=+∞T=+∞

④P=T=6T=6

T=8T=+∞T=+∞

⑤P=T=6

T=8T=9T=12

⑥P=T=8T=10T=10

⑦P=T=9T=11再無(wú)其它T標(biāo)號(hào)，所以

T(V8)=P(V8)=10;minL(μ)=10⑧P=T=10V1V2V3V4V5V6V7V8①P=0T=+∞T=+∞T由此看到，此方法不僅求出了從V1

到V8

的最短路長(zhǎng)，同時(shí)也求出了從V1

到任意一點(diǎn)的最短路長(zhǎng)。將從V1

到任一點(diǎn)的最短路權(quán)標(biāo)在圖上，即可求出從V1

到任一點(diǎn)的最短路線。本例中V1

到V8

的最短路線是：

v1→v2→v5→v6→v8

由此看到，此方法不僅求出了從V1到V8623121641036234210623121641036234210（二）、逐次逼近法算法的基本思路與步驟：首先設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個(gè)點(diǎn)vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長(zhǎng)，P1i表示從v1到vi的最短路長(zhǎng)，則有下列方程：開(kāi)始時(shí)，令即用v1到vj的直接距離做初始解。從第二步起，使用遞推公式：求，當(dāng)進(jìn)行到第t步，若出現(xiàn)則停止計(jì)算，即為v1到各點(diǎn)的最短路長(zhǎng)。（二）、逐次逼近法例二、

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23

0000v260

2

-1-5-5-5v3

-30-5

1

-2-2-2-2v48

0

2

3-7-7-7v5

-1

0

1-3-3v6

1017

-1-1-1v7

-1

0

5-5-5v8

-3

-50

66求圖中v1到各點(diǎn)的最短路例二、

－18v1v2v3v4v5－26－3－5－1－3－5

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）

－18v1v2v3v4v5－26－3－5－1－3－521－例三、求：5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。解：（1）分析：可行的購(gòu)置方案（更新計(jì)劃）是很多的，如：1）每年購(gòu)置一臺(tái)新的，則對(duì)應(yīng)的費(fèi)用為：

11+11+12+12+13+5+5+5+5+5=842)第一年購(gòu)置新的，一直用到第五年年底，則總費(fèi)用為：11+5+6+8+11+18=59

顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。第i年度

12345購(gòu)置費(fèi)1111121213設(shè)備役齡0-11-22-33-44-5維修費(fèi)用

5681118例三、求：5年內(nèi)，哪些年初購(gòu)置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。（2）方法：將此問(wèn)題用一個(gè)賦權(quán)有向圖來(lái)描述，然后求這個(gè)賦權(quán)有向圖的最短路。求解步驟：1）畫賦權(quán)有向圖：設(shè)Vi

表示第i年初，(Vi,Vj)表示第i年初購(gòu)買新設(shè)備用到第j年初（j-1年底），而Wij

表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從V1

到V6的一條路。2）求解（標(biāo)號(hào)法）（2）方法：將此問(wèn)題用一個(gè)賦權(quán)有向圖來(lái)描述，然后求這個(gè)賦權(quán)W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12