离散数学最短路径和关键路径

《离散数学最短路径和关键路径》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.4最短路径与关键路径带权图最短路径与Dijkstra标号法PERT图与关键路径1最短路径带权图G=,其中w:ER.eE,w(e)称作e的权.e=(vi,vj),记w(e)=wij.若vi,vj不相邻,记wij=.设L是G中的一条路径,L的所有边的权之和称作L的权,记作w(L).u和v之间的最短路径:u和v之间权最小的通路.例1L1=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.2标号法(E.W.Dijkstra,1959)设带权图G

2、=,其中eE,w(e)0.设V={v1,v2,,vn},求v1到其余各顶点的最短路径p标号(永久性标号):第r步获得的v1到vi最短路径的权t标号(临时性标号):第r步获得的v1经过p标号顶点到达vi的路径的最小权,是v1到vi的最短路径的权的上界第r步通过集Pr={v

3、v在第r步已获得永久性标号}第r步未通过集Tr=V-Pr3标号法(续)1.v1获p标号:=0,P0={v1},T0=V-{v1},vj(j=2,3,,n)获t标号:=wij.令r1.2.设,vi获得p标号:.令Pr=Pr-1{vi},T

4、r=Tr-1-{vi}.若Tr=,则结束.3.vjTr,令令r=r+1,转2.算法:4标号法(续)例1(续)求v0到v5的最短路径v0v1v2v3v4v5001411/v038623/v184374/v21047/v4959/v3w013749=v0v1v2v4v3v5,w()=9vir5PERT图(计划评审技术图)设有向图G=,vVv的后继元集+(v)={x

5、xVE}v的先驱元集-(v)={x

6、xVE}PERT图:满足下述条件的n阶有向带权图D=,

7、(1)D是简单图,(2)D中无回路,(3)有一个入度为0的顶点,称作始点;有一个出度为0的顶点,称作终点.通常边的权表示时间,始点记作v1,终点记作vn6关键路径关键路径:PETR图中从始点到终点的最长路径vi的最早完成时间TE(vi):从始点v1沿最长路径到vi所需的时间TE(v1)=0TE(vi)=max{TE(vj)+wji

8、vj-(vi)},i=2,3,,nvi的最晚完成时间TL(vi):在保证终点vn的最早完成时间不增加的条件下,从始点v1最迟到达vi的时间TL(vn)=TE(vn)TL(vi)=min{TL(vj

9、)-wij

10、vj+(vi)},i=n-1,n-2,,17关键路径(续)vi的缓冲时间TS(vi)=TL(vi)-TE(vi),i=1,2,,nvi在关键路径上TS(vi)=08例2求PERT图中各顶点的最早完成时间,最晚完成时间,缓冲时间及关键路径.解最早完成时间TE(v1)=0TE(v2)=max{0+1}=1TE(v3)=max{0+2,1+0}=2TE(v4)=max{0+3,2+2}=4TE(v5)=max{1+3,4+4}=8TE(v6)=max{2+4,8+1}=9TE(v7)=max{1+4,2+4}=6T

11、E(v8)=max{9+1,6+6}=129例2(续)最晚完成时间TL(v8)=12TL(v7)=min{12-6}=6TL(v6)=min{12-1}=11TL(v5)=min{11-1}=10TL(v4)=min{10-4}=6TL(v3)=min{6-2,11-4,6-4}=2TL(v2)=min{2-0,10-3,6-4}=2TL(v1)=min{2-1,2-2,6-3}=010例2(续)缓冲时间TS(v1)=0-0=0TS(v2)=2-1=1TS(v3)=2-2=0TS(v4)=6-4=2TS(v5=10-8=2TS(v

12、6)=11-9=2TS(v7)=6-6=0TS(v8)=12-12=0关键路径:v1v3v7v811