算法10有向无环图及其应用关键路径.ppt

关键路径 AOV网 ActivityOnVertex 顶点表示活动 弧表示优先关系 只表示活动之间定性的拓扑关系 不表示活动之间定量的时序关系 2 关键路径 1 问题提出 假设以有向网表示一个施工流图 用顶点表示事件 弧表示活动 弧上的权值表示完成该项子工程所需时间 每个事件表示在它之前的活动已完成 在它之后的活动可以开始 3 例设一个工程有11项活动 9个事件事件V1 表示整个工程开始事件V9 表示整个工程结束问题 1 完成整项工程至少需要多少时间 2 哪些活动是影响工程进度的关键 关键路径 CriticalPath 汇点 源点 4 AOE ActivityOnEdges 网络 如果在带权DAG图中用有向边表示一个工程中的活动 Activity 用边上权值表示活动持续时间 Duration 用顶点表示事件 Event 则这样的有向图叫做用边表示活动的网络 简称AOE ActivityOnEdges 网络 2 定义 路径长度 从源点到汇点可能有多条有向路径 路径上各活动所需时间之和叫该路径的路径长度关键路径 具有最大路径长度的路径叫做关键路径 上图的关键路径有a1 a4 a7 a10和a1 a4 a8 a11 它们的路径长度均为18关键活动 关键路径上的所有活动都叫做关键活动 对上图的AOE 关键活动是a1 a4 a7 a8 a10 a11关键活动上持续时间的变化可能影响整个工程的工期 汇点 源点 6 路径长度 路径上各活动持续时间之和关键路径 路径长度最长的路径Ve j 表示事件Vj的最早发生时间Vl j 表示事件Vj的最迟发生时间e i 表示活动ai的最早开始时间l i 表示活动ai的最迟开始时间l i e i 表示完成活动ai的机动时间关键活动 关键路径上的活动 即l i e i 的活动 关键路径 CriticalPath AOE中有关概念 7 3 如何找e i l i 的关键活动 设活动ai用弧表示 其持续时间记为 dut 则有 1 e i Ve j 2 l i Vl k dut 如何求Ve j 和Vl j 8 如何求Ve j 和Vl j 关键路径 CriticalPath 1 从ve 1 0开始向前递推 2 从vl n ve n 开始向后递推 9 4 求关键路径步骤 1 求Ve i 2 求Vl j 3 求e i 4 求l i 5 计算l i e i 关键路径 CriticalPath 汇点 源点 事件Vi的最早可能开始时间Ve i 是从源点V1到顶点Vi的最长路径长度 如Ve 5 6 1 7 事件Vi的最迟允许开始时间Vl i 是工程按期完成情况下Vi的最迟允许开始时间 如Vl 5 18 4 7 7 Vl 6 18 4 4 10 活动ak的最早可能开始时间e k 设ak是在上 e k 是从源点到Vi的最长路径长度 故e k Ve i 例如 e 4 Ve 2 6 e 6 Ve 4 5 汇点 源点 活动ak的最迟允许开始时间l k 是工程按期完成情况下ak的最迟允许开始时间 设ak在上 并ak的持续时间为dur l k Vl j dur 例如 l 4 Vl 5 dur 7 1 6l 6 Vl 6 dur 10 2 8 活动ak的机动时间 是l k e k 例如a6的机动时间l 6 e 6 8 5 3a4的机动时间l 4 e 4 6 6 0 关键活动上有l k e k 12 V1V2V3V4V5V6V7V8V9 064577161418 0668710161418 a1a2a3a4a5a6a7a8a9a10a11 例 1 e i Ve j 2 l i Vl k dut 13 5 算法思想 1 建立AOE网 2 从源点v0出发 令ve 0 0 边进行拓扑排序 边计算其余各顶点的ve i 若图中有回路则结束 3 从汇点vn 1出发 vl n 1 el n 1 按逆拓扑有序的顺序求vl i i n 2 0 4 根据各点的ve和vl值 求每条弧的最早开始时间e s 和最迟开始时间l s 若某弧满足条件e s l s 则是关键活动 关键路径 CriticalPath 14 6 求关键路径算法 在此算法中需要对邻接表中单链表的结点加以修改 在各结点中增加一个int域info 记录该边的权值 关键路径 CriticalPath 15 拓扑排序算法 计算ve statustopLogicalSort ALGraphG Stack topLogicalSort 16 求关键活动算法 voidcriticalPath ALGraphG if topLogicalSort G T returnERROR vl 0 G vexnum 1 ve G vexnum 1 while StackEmpty T 按逆拓扑序求vl pop T j for p G vertices j firstarc p p p next k p adjvex dut p info if vl k dut vl j vl j vl kj dut forp while k k k 17 求ee el和关键活动for j 0 jadjvex dut p info ee ve j el vl k dut if ee el tag elsetag printf j k dut e