1、1,7.4 最短路徑與關(guān)鍵路徑,帶權(quán)圖 最短路徑與Dijkstra標(biāo)號法 PERT圖與關(guān)鍵路徑,2,最短路徑,帶權(quán)圖G=, 其中w:ER. eE, w(e)稱作e的權(quán). e=(vi,vj), 記w(e)=wij . 若vi,vj不 相鄰, 記wij =. 設(shè)L是G中的一條路徑, L的所有邊的權(quán)之和稱作L的 權(quán), 記作w(L). u和v之間的最短路徑: u和v之間權(quán)最小的通路.,例1 L1=v0v1v3v5, w(L1)=10, L2=v0v1v4v5, w(L2)=12, L3=v0v2v4v5, w(L3)=11.,3,標(biāo)號法(E.W.Dijkstra, 1959),設(shè)帶權(quán)圖G=, 其中eE

2、, w(e)0. 設(shè)V=v1,v2,vn, 求v1到其余各頂點(diǎn)的最短路徑 p標(biāo)號(永久性標(biāo)號) : 第r步獲得的v1到vi最短路徑的 權(quán) t標(biāo)號(臨時性標(biāo)號) : 第r步獲得的v1經(jīng)過p標(biāo)號頂點(diǎn) 到達(dá)vi的路徑的最小權(quán), 是v1到vi的最短路徑的權(quán)的上 界 第r步通過集Pr=v | v在第r步已獲得永久性標(biāo)號 第r步未通過集Tr=V-Pr,4,標(biāo)號法(續(xù)),5,標(biāo)號法(續(xù)),6,PERT圖(計(jì)劃評審技術(shù)圖),設(shè)有向圖G=, vV v的后繼元集 +(v)=x|xVE v的先驅(qū)元集 -(v)=x|xVE PERT圖:滿足下述條件的n階有向帶權(quán)圖D=, (1) D是簡單圖, (2) D中無回路, (

3、3) 有一個入度為0的頂點(diǎn), 稱作始點(diǎn); 有一個出度為0 的頂點(diǎn), 稱作終點(diǎn). 通常邊的權(quán)表示時間, 始點(diǎn)記作v1, 終點(diǎn)記作vn,7,關(guān)鍵路徑,關(guān)鍵路徑: PETR圖中從始點(diǎn)到終點(diǎn)的最長路徑 vi的最早完成時間TE(vi): 從始點(diǎn)v1沿最長路徑到vi 所需的時間 TE(v1)=0 TE(vi)=maxTE(vj)+wji|vj -(vi), i=2,3,n vi的最晚完成時間TL(vi): 在保證終點(diǎn)vn的最早完成 時間不增加的條件下, 從始點(diǎn)v1最遲到達(dá)vi的時間 TL(vn)=TE(vn) TL(vi)=minTL(vj)-wij|vj +(vi), i=n-1,n-2,1,8,關(guān)鍵路

4、徑(續(xù)),vi的緩沖時間TS(vi)=TL(vi)-TE(vi), i=1,2,n vi在關(guān)鍵路徑上TS(vi)=0,9,例2 求PERT圖中各頂點(diǎn)的最早完成時間, 最晚完成 時間, 緩沖時間及關(guān)鍵路徑. 解 最早完成時間 TE(v1)=0 TE(v2)=max0+1=1 TE(v3)=max0+2,1+0=2 TE(v4)=max0+3,2+2=4 TE(v5)=max1+3,4+4=8 TE(v6)=max2+4,8+1=9 TE(v7)=max1+4,2+4=6 TE(v8)=max9+1,6+6=12,10,例2(續(xù)) 最晚完成時間 TL(v8)=12 TL(v7)=min12-6=6 TL(v6)=min12-1=11 TL(v5)=min11-1=10 TL(v4)=min10-4=6 TL(v3)=min6-2,11-4,6-4=2 TL(v2)=min2-0,10-3,6-4=2 TL(v1)=min2-1,2-2,6-3=0,11,例2(續(xù)) 緩沖時間 TS(v1)=0-0=0 TS(v2)=2-1=1 TS(v3)=2-2=0 TS(v4)=6-4=2 TS(v5=10-8=2