离散数学 最短路径和关键路径.ppt_第1页
离散数学 最短路径和关键路径.ppt_第2页
离散数学 最短路径和关键路径.ppt_第3页
离散数学 最短路径和关键路径.ppt_第4页
离散数学 最短路径和关键路径.ppt_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1 7 4最短路径与关键路径 带权图最短路径与Dijkstra标号法PERT图与关键路径 2 最短路径 带权图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 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步未通过集Tr V Pr 4 标号法 续 5 标号法 续 6 PERT图 计划评审技术图 设有向图G v Vv的后继元集 v x x V E v的先驱元集 v x x V E PERT图 满足下述条件的n阶有向带权图D 1 D是简单图 2 D中无回路 3 有一个入度为0的顶点 称作始点 有一个出度为0的顶点 称作终点 通常边的权表示时间 始点记作v1 终点记作vn 7 关键路径 关键路径 PETR图中从始点到终点的最长路径vi的最早完成时间TE vi 从始点v1沿最长路径到vi所需的时间TE v1 0TE vi max TE vj wji vj vi i 2 3 nvi的最晚完成时间TL vi 在保证终点vn的最早完成时间不增加的条件下 从始点v1最迟到达vi的时间TL vn TE vn TL vi min TL vj wij vj vi i n 1 n 2 1 8 关键路径 续 vi的缓冲时间TS vi TL vi TE vi i 1 2 nvi在关键路径上 TS vi 0 9 例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 6TE v8 max 9 1 6 6 12 10 例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 0 11 例2 续 缓冲时间TS v1 0 0 0TS v2 2 1 1TS v3 2 2 0TS v4 6
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论