关键路径.pptx

关键路径语言: java 环境: eclipse 软件学院 2010 级1班王彤彤 201000301201 如果在无环的带权有向图中,用有向边表示一个工程中的活动,用边上权值表示活动持续时间,用顶点表示事件,则这样的有向图叫做用边表示活动的网络,简称 AOE (Activity On Edges) 网络。并且在 AOE 网络中只有一个源点与一个汇点。关键路径完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。。在关键路径上的活动都是关键活动。事件 i的最早发生时间 ve[i]是从源点到该点的最长路径长度。(源点 1的ve [1] 为0)事件 i的最早发生时间 Ve [i]即为“所有指向 i的点的最早发生时间+该点与 i之间边的权值”中的最大值。公式: Ve (i )=max{ ve (j)+ dut (< j,i >)} j ∈ T 其中 T是以顶点 vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。事件 i的最晚发生时间 vl[i]是在汇点 n保证在 ve [n] 时刻完成的前提下, i开始的最晚的时间。(汇点 n的vl [n]= ve [n] ) 事件 i的最晚发生时间 Vl[i]即为“i指向的所有的点的最晚发生时间-该点与 i之间边的权值”中的最小值。公式: vl(i )= min{ vl (k)- dut (< j,k >)} k ∈ S 其中 S 是以顶点 vj是头节点的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。如果得到的拓朴有序序列中顶点的个数小于网中顶点个数 n,则说明网中有环,不能求出关键路径,算法结束。活动 ak在< i,j>的边上,则活动的最早发生时间 e[k]= ve[i],最晚发生时间 l[k]= vl [j]- dur (< i,j >). dur (< i,j >)为完成 ak所需的时间。一个活动 ak的 e[k]=l[k] 时,该活动为关键活动。例如下图 1为一 AOE 网络。求事件 i的ve[i] 求事件 i的 vl[i]求活动 k的 e[k] 和 l[k] 关键路径为: