離散數(shù)學(xué)-耿素云PPT(第5版)5.4

15.4

最短路徑,關(guān)鍵路徑與著色帶權(quán)圖最短路徑與Dijkstra標(biāo)號(hào)法項(xiàng)目網(wǎng)絡(luò)圖與關(guān)鍵路徑著色問題2最短路徑帶權(quán)圖G=<V,E,w>,其中w:ER.

e

E,w(e)稱作e的權(quán).e=(vi,vj),記w(e)=wij.若vi,vj不相鄰,記wij=.通路L的權(quán):L的所有邊的權(quán)之和,記作w(L).u和v之間的最短路徑:u和v之間權(quán)最小的通路.例

L1=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.3標(biāo)號(hào)法(E.W.Dijkstra,1959)設(shè)帶權(quán)圖G=<V,E,w>,其中

e

E,w(e)0.設(shè)V={v1,v2,,vn},求v1到其余各頂點(diǎn)的最短路徑1.令l1

0,p1

,lj

+

,pj

,j=2,3,

,n,P={v1},T=V-{v1},k

1,t

1./

表示空2.對(duì)所有的vj

T且(vk,vj)

E

令l

min{lj,lk+wkj},

若l=lk+wkj,則令lj

l,pj

vk.3.求li=min{lj|vj

Tt}.

令P

P

{vi},T

T-{vi},k

i.4.令t

t+1,

若t<n,則轉(zhuǎn)2.4Dijkstra標(biāo)號(hào)法實(shí)例例

求v0到v5的最短路徑

t

v0

v1

v2

v3

v4

v5

1(0,

)*(+

,

)(+

,

)(+

,

)(+

,

)(+

,

)2(1,v0)*(4,v0)(+

,

)(+

,

)(+

,

)3(3,v1)*(8,v1)(6,v1)(+

,

)4(8,v1)(4,v2)*(+

,

)5(7,v4)*(10,v4)6(9,v3)*v0到v5的最短路徑:v0v1v2v4v3v5,d(v0,v5)=95項(xiàng)目網(wǎng)絡(luò)圖項(xiàng)目網(wǎng)絡(luò)圖:表示項(xiàng)目的活動(dòng)之間前后順序一致的帶權(quán)有向圖.邊表示活動(dòng),邊的權(quán)是活動(dòng)的完成時(shí)間,頂點(diǎn)表示事項(xiàng)(項(xiàng)目的開始和結(jié)束、活動(dòng)的開始和結(jié)束).要求:(1)有一個(gè)始點(diǎn)(入度為0)和一個(gè)終點(diǎn)(出度為0).(2)任意兩點(diǎn)之間只能有一條邊.(3)沒有回路.

(4)每一條邊始點(diǎn)的編號(hào)小于終點(diǎn)的編號(hào).A引入虛活動(dòng)ABBCC例6

活動(dòng)ABCDEFGHIJKL緊前活動(dòng)

AAA,BA,BA,BC,HD,FE,IG,K時(shí)間(天)12343442461141235678ABCDEFGHIJKL1234344246117關(guān)鍵路徑關(guān)鍵路徑:項(xiàng)目網(wǎng)絡(luò)圖中從始點(diǎn)到終點(diǎn)的最長(zhǎng)路徑關(guān)鍵活動(dòng):關(guān)鍵路徑上的活動(dòng)設(shè)D=<V,E,W>,V={1,2,,n},1是始點(diǎn),n是終點(diǎn).(1)事項(xiàng)i的最早完成時(shí)間ES(vi):i最早可能開始的時(shí)間,即從始點(diǎn)到i的最長(zhǎng)路徑的長(zhǎng)度.

ES(1)=0ES(i)=max{ES(j)+wji|<j,i>

E},i=2,3,,n(2)事項(xiàng)i的最晚完成時(shí)間LF(i):在不影響項(xiàng)目工期的條件下,事項(xiàng)i最晚必須完成的時(shí)間.LF(n)=ES(n)LF(i)=min{LF(j)-wij|<i,j>

E},i=n-1,n-2,,18關(guān)鍵路徑(續(xù))(3)活動(dòng)<i,j>的最早開始時(shí)間ES(i,j):<i,j>最早可能開始時(shí)間.(4)活動(dòng)<i,j>的最早完成時(shí)間EF(i,j):<i,j>最早可能完成時(shí)間.(5)活動(dòng)<i,j>的最晚開始時(shí)間ES(i,j):在不影響項(xiàng)目工期的條件下,<i,j>最晚必須開始的時(shí)間.(6)活動(dòng)<i,j>的最晚完成時(shí)間ES(i,j):在不影響項(xiàng)目工期的條件下,<i,j>最晚必須完成的時(shí)間.(7)活動(dòng)<i,j>的緩沖時(shí)間SL(i,j):

SL(i,j)=LS(i,j)-ES(i,j)=LF(i,j)-EF(i,j)顯然,ES(i,j)=ES(i),EF(i,j)=ES(i)+wij,

LF(i,j)=LF(j),LS(i,j)=LF(j)-wij,9事項(xiàng)的最早開始時(shí)間

TE(1)=0TE(2)=max{0+1}=1TE(3)=max{0+2,1+0}=2TE(4)=max{0+3,2+2}=4TE(5)=max{1+3,4+4}=8TE(6)=max{2+4,8+1}=9TE(7)=max{1+4,2+4}=6TE(8)=max{9+1,6+6}=12例(續(xù))10事項(xiàng)的最晚完成時(shí)間

TL(8)=12TL(7)=min{12-6}=6TL(6)=min{12-1}=11TL(5)=min{11-1}=10TL(4)=min{10-4}=6TL(3)=min{6-2,11-4,6-4}=2TL(2)=min{2-0,10-3,6-4}=2TL(1)=min{2-1,2-2,6-3}=0例(續(xù))11總工期:12天關(guān)鍵路徑:v1v3v7v8關(guān)鍵活動(dòng):B,F,J例(續(xù))著色定義

設(shè)無向圖G無環(huán),對(duì)G的每個(gè)頂點(diǎn)涂一種顏色，使相鄰的頂點(diǎn)涂不同的顏色，稱為圖G的一種點(diǎn)著色,簡(jiǎn)稱著色．若能用k種顏色給G的頂點(diǎn)著色，則稱G是k-可著色的．圖的著色問題:用盡可能少的顏色給圖著色.12例121222111111222322221111311122234例例2131122221112123213321232314應(yīng)用有n項(xiàng)工作,每項(xiàng)工作需要一天的時(shí)間完成.有些工作由于需要相同的人員或設(shè)備不能同時(shí)進(jìn)行,問至少需要幾天才能完成所有的工作?計(jì)算機(jī)有k個(gè)寄存器,現(xiàn)正在編譯一個(gè)程序,要給每一個(gè)變量分配一個(gè)寄存器.如果兩個(gè)變量要在同一時(shí)刻使用,則不能把它們分配給同一個(gè)寄存器.如何給變量分配寄存器?無線交換設(shè)備的波長(zhǎng)分配.有n臺(tái)設(shè)備和k個(gè)發(fā)射波長(zhǎng),要給每一臺(tái)設(shè)備分配一個(gè)波長(zhǎng).如果兩臺(tái)設(shè)備靠得太近,則不能給它們分配相同的波長(zhǎng),以防止干擾.如何分配波長(zhǎng)?14例例3學(xué)生會(huì)下設(shè)6個(gè)委員會(huì),第一委員會(huì)={張,李,王},第二委員會(huì)={李,趙,劉},第三委員會(huì)={