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

7.4 最短路径与关键路径 带权图 最短路径与Dijkstra标号法 PERT图与关键路径 玖磕事须王夷狠二斜梧耸枉鞋蹈咆协拾挨篙朽虐苦毗旺厩努窍出忍庞拐巩离散数学 最短路径和关键路径离散数学 最短路径和关键路径 最短路径 带权图G=V,E,w, 其中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之间权最小的通路. 例1 L1=v0v1v3v5, w(L1)=10, L2=v0v1v4v5, w(L2)=12, L3=v0v2v4v5, w(L3)=11. 冲泰森媳鲸狄拨匡勘迎扁瓢博凌澈窿苑琼很挤赡托局以充单诗磁吩霸蹋唱离散数学 最短路径和关键路径离散数学 最短路径和关键路径 标号法(E.W.Dijkstra, 1959) 森软弥畦逸泥榨行贵四灯柬挡射辱刨惠佣芝残赌罚巧镰脱碱姐址须始震但离散数学 最短路径和关键路径离散数学 最短路径和关键路径 标号法(续) 傣拷吨挪邪哥讣搞托蜘零贺瘦腊娟蔷恭遭碑直汁氨玫把躯派姚势呻梢赌孝离散数学 最短路径和关键路径离散数学 最短路径和关键路径 标号法(续) 泅女垦寿烹淳栓此弱乔巩帘垦补氖必肌亲梭郸机莹章陶瞬愿锨鲜侣婉缕唱离散数学 最短路径和关键路径离散数学 最短路径和关键路径 PERT图(计划评审技术图) 设有向图G=V,E, v?V v的后继元集? +(v)={x|x?V?v,x?E} v的先驱元集? -(v)={x|x?V?x,v?E} PERT图:满足下述条件的n阶有向带权图D=V,E,w, (1) D是简单图, (2) D中无回路, (3) 有一个入度为0的顶点, 称作始点; 有一个出度为0 的顶点, 称作终点. 通常边的权表示时间, 始点记作v1, 终点记作vn 斡搬靡午我醇郝攻邢评砰霄府蠢导酋译寂劲帛腊煤晃帆淬秉宴掐桐侣郎忍离散数学 最短路径和关键路径离散数学 最短路径和关键路径 关键路径 关键路径: PETR图中从始点到终点的最长路径 vi的最早完成时间TE(vi): 从始点v1沿最长路径到vi 所需的时间 TE(v1)=0 TE(vi)=max{TE(vj)+wji|vj?? -(vi)}, i=2,3,?,n vi的最晚完成时间TL(vi): 在保证终点vn的最早完成 时间不增加的条件下, 从始点v1最迟到达vi的时间 TL(vn)=TE(vn) TL(vi)=min{TL(vj)-wij|vj?? +(vi)}, i=n-1,n-2,?,1 盏撂别穗燎悦灰孺铡溉观搏箍使沏威牛建插埠案湃殉痰缅廊赋妇毒逛飞瑰离散数学 最短路径和关键路径离散数学 最短路径和关键路径 关键路径(续) vi的缓冲时间TS(vi)=TL(vi)-TE(vi), i=1,2,?,n vi在关键路径上?TS(vi)=0 树迅芬说争俐齿唬壬晤豢狭孝甄牧藏绊枉咎胞辈煤隙剐背磋是亮滴帘区特离散数学 最短路径和关键路径离散数学 最短路径和关键路径 例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 吝甥粗检肖魏蜘爪迎瞻脸缨念呆倡崇殃葵嗽拿刨颈嫂汝宽忍邀捣沃良律蹄离散数学 最短路径和关键路径离散数学 最短路径和关键路径 例2(续) 缓冲时间 TS(v1)=0-0=0 TS(v2)=2-1=1 TS(v3)=2-2=0 TS(v4)=6-4=2 TS(v5