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

《离散数学最短路径和关键路径.pptx》由会员分享，可在线阅读，更多相关《离散数学最短路径和关键路径.pptx（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、17.4 最短路径与关键路径最短路径与关键路径n带权图带权图n最短路径与最短路径与Dijkstra标号法标号法nPERT图与关键路径图与关键路径2最短路径最短路径带权图带权图G=,其中其中w:ER.e E,w(e)称作称作e的的权权.e=(vi,vj),记记w(e)=wij.若若vi,vj不不相邻相邻,记记wij=.设设L是是G中的一条路径中的一条路径,L的所有边的权之和称作的所有边的权之和称作L的的权权,记作记作w(L).u和和v之间的之间的最短路径最短路径:u和和v之间权最小的通路之间权最小的通路.例例1 L1=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,

2、L3=v0v2v4v5,w(L3)=11.3标号法标号法(E.W.Dijkstra,1959)设带权图设带权图G=,其中其中 e E,w(e)0.设设V=v1,v2,vn,求求v1到其余各顶点的最短路径到其余各顶点的最短路径p标号标号(永久性标号永久性标号):第第r步获得的步获得的v1到到vi最短路径的最短路径的权权t标号标号(临时性标号临时性标号):第第r步获得的步获得的v1经过经过p标号顶点标号顶点到达到达vi的路径的最小权的路径的最小权,是是v1到到vi的最短路径的权的上的最短路径的权的上界界第第r步通过集步通过集Pr=v|v在第在第r步已获得永久性标号步已获得永久性标号第第r步未通过集

3、步未通过集Tr=V-Pr4标号法标号法(续续)1.v1获获p标号标号:=0,P0=v1,T0=V-v1,vj(j=2,3,n)获获t 标标 号号:=wij.令令r1.2.设设 ,vi获得获得p标号标号:.令令 Pr=Pr-1 vi,Tr=Tr-1-vi.若若Tr=,则结束则结束.3.vj Tr,令令 令令r=r+1,转转2.算法算法:5标号法标号法(续续)例例1(续续)求求v0到到v5的最短路径的最短路径 v0 v1 v2 v3 v4 v5 0 0 1 4 1 1/v0 3 8 6 2 3/v1 8 4 3 7 4/v2 10 4 7/v4 9 5 9/v3 w 0 1 3 7 4 9 =v0

4、v1v2v4v3v5,w()=9vir6PERT图图(计划评审技术图计划评审技术图)设有向图设有向图G=,v Vv的的后继元集后继元集 +(v)=x|x V Ev的的先驱元集先驱元集 -(v)=x|x V EPERT图图:满足下述条件的满足下述条件的n阶有向带权图阶有向带权图D=,(1)D是简单图是简单图,(2)D中无回路中无回路,(3)有一个入度为有一个入度为0的顶点的顶点,称作称作始点始点;有一个出度为有一个出度为0 的顶点的顶点,称作称作终点终点.通常边的权表示时间通常边的权表示时间,始点记作始点记作v1,终点记作终点记作vn7关键路径关键路径关键路径关键路径:PETR图中从始点到终点的

5、最长路径图中从始点到终点的最长路径vi的最早完成时间的最早完成时间TE(vi):从始点从始点v1沿最长路径到沿最长路径到vi所需的时间所需的时间 TE(v1)=0 TE(vi)=maxTE(vj)+wji|vj -(vi),i=2,3,nvi的最晚完成时间的最晚完成时间TL(vi):在保证终点在保证终点vn的最早完成的最早完成时间不增加的条件下时间不增加的条件下,从始点从始点v1最迟到达最迟到达vi的时间的时间 TL(vn)=TE(vn)TL(vi)=minTL(vj)-wij|vj +(vi),i=n-1,n-2,18关键路径关键路径(续续)vi的缓冲时间的缓冲时间TS(vi)=TL(vi)

6、-TE(vi),i=1,2,nvi在关键路径上在关键路径上TS(vi)=09例例2 求求PERT图中各顶点的最早完成时间图中各顶点的最早完成时间,最晚完成最晚完成时间时间,缓冲时间及关键路径缓冲时间及关键路径.解解 最早完成时间最早完成时间 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=1210例例2(续续)最晚完成时间最晚完成时间 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=011例例2(续续)缓冲时间缓冲时间 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 TS(v6)=11-9=2 TS(v7)=6-6=0 TS(v8)=12-12=0关键路径关键路径:v1v3v7v8微信公众平台开发 枒痋爿