第10章 拓展补充：图的应用（关键路径及DJ最短路径）《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

6学科网 WWw.ZXXK.CON 图的应用 6学科网 WWw.ZXXK.COM 一 ：关键路径的求解 问题的提出： 市政工程常常需要进行路面改造，修路过程 中给周围居民及行人带来诸多不便，快速、 完善的修好一条路显然是很重要的 而当前的路上、路下都包含了很多的内容 路面有绿化、路灯、路下更为复杂，各种 水管、电缆等，显然这是一个系统工程。 6 学科网 ●1 下表是项目流程，我们的目的是如何科学安排 WWw.ZXXK.CON 尽快完成该项目 事件 事件名 项目 目代 目工 目前期事 目结束事 码 期 件 件 V1 项目开工，路面挖开 铺水管 A1 6 V1 V2 V2 水管铺设成功 铺电缆 A2 4 V1 V3 V3 电缆铺设成功 铺通讯线 A3 5 V1 V4 V4 通讯线铺设成功 密封水管 A4 1 V2 V5 V5 水管、强电数设成功 绝缘强电 A5 1 V3 V5 V6 通讯电缆敷设成功 绝缘通讯电缆 A6 3 V4 V6 V7 水管、强点测试通过 强电、水管测试 A7 9 V5 V7 V8 路面铺好，通讯设置成功 铺路面 A8 7 V5 V8 V9 项目完工 配置通讯电路 A9 4 V6 V8 装路灯 A10 2 V7 V9 绿化 A11 4 V8 V9 6学科网 Www.ZXXK.COM ●为此，首先基于该流程，画出AOE网 V7 V2 源点 a41 a7=9 a10=2 a1=6 V5 V1 a51 a8=7 V9 a2=4 V3 V8 a11=4 a345 汇点 a9≥4 V4 a6=2 V6 6学科网 WWw.ZXXK.CON 所谓科学决策，就是又快又好的完成该项目 介绍以下几个名词： 1：事件的最早发生时间 2:事件的至迟发生时间 3:项目的最早发生时间 4:项目的至迟发生时间 6学科网 ·针对本项目，进行以下计算： WWw.ZXXK.COM Ve(1)=0 V1(9)=18 Ve(2)=6 V1(8)=18-4=14 Ve(3)=4 VI(7)=18-2=16 Ve(4)=5 V1(6)=14-4=10 Ve(5)=max(7,5)=5 Vl(5)=min(14-7,16-9)=7 Ve(6)=5+2=7 V1(4)=10-2=8 Ve(7)=7+9=16 V1(3)=7-1=6 Ve(8)=max(14,11)=1l(2)=7-1=6 4 Ve(9)=max(18,18)=1Wl(1)=min(6-6,6-4,8-5) 8 =0 6学科网 Www.ZXXK.COM 。项目的最早开始时间，与其前期事件的最 早发生时间一致 ●项目的至迟发生时间等于该项目结束事件 的至迟时间减去该项目耗费时间 由此，我们得到下表项目的至迟时间和至 早时间 6学科网 WWw.ZXXK.COM 项目的至早时间 项目的至迟时间 Ea1=0 La1=0 Ea2=0 La2=2 Ea3=0 La3=3 Ea4=6 La4=6 Ea5=4 La5=6 Ea6=5 La6=8 Ea7=7 La7=7 Ea8=7 La8=7 Ea9=7 La9=10 Ea10=16 La10=16 Ea11=14 La11=14 进一步得到下表，从而求出关键路径 6学科网 WWw.ZXXK.COM 活动 al a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 E 0 0 0 6 4 5 7 7 7 16 14 0 23 6 6 87 7 10 16 14 L-E 0 2 3 02 30 03 0 0 6 学科网 WWw.ZXXK.COM 二、物流公司的路径选择 物流公司经常性的需要从某一个城市向其他 不同城市运送货物，城市之间的相互交通 及其费用构成了一个有向带权网，选择最 经济的交通路线，显然是一个重要的问题