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

1;最短路径;标号法(E.W.Dijkstra,1959)

设带权图G=V,E,w,其中?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步未通过集Tr=V-Pr;标号法(续);标号法(续);PERT图(计划评审技术图);关键路径;关键路径(续);例2求PERT图中各顶点的最早完成时间,最晚完成

时间,缓冲时间及关键路径.

解最早完成时间

TE(v1)=0

TE(v2)=max{0+1}=1

TE(v3)=max{0+2,1+0}=2

TE(v4)=max{0+3,2+2}=4

TE(v5)=max{1+3,4+4}=8

TE(v6)=max{2+4,8+1}=9

TE(v7)=max{1+4,2+4}=6

TE(v8)=max{9+1,6+6}=12;例2(续)

最晚完成时间

TL(v8)=12

TL(v7)=min{12-6}=6

TL(v6)=min{12-1}=11

TL(v5)=min{11-1}=10

TL(v4)=min{10-4}=6

TL(v3)=min{6-2,11-4,6-4}=2

TL(v2)=min{2-0,10-3,6-4}=2

TL(v1)=min{2-1,2-2,6-3}=0;11;微信公众平台开发枒痋爿