计算关键路径

1、五、五、 计算关键路径计算关键路径【例题】计算能影响整个计划完成时间的关键活动【例题】计算能影响整个计划完成时间的关键活动工厂的工程计划用一张有向图表示，有向图的结点表示事件，有向边表示活动，边上的权标明一项活动需要的时间。结点所表示的事件实际上就是它入边代表的活动均已完成，出边代表的活动可以开始这样一种状态。例如上图含12项活动、9个事件。其中事件v1表示开始时活动a1、a2、a3并行实施；事件v5代表活动a4、a5已经完成，活动a7、a8可以开始。V9表示整个计划完成。活动依事件的顺序要求进行。例如活动a4、a5、a6只有当事件v2、v3、v4分别发生后才能进行，而它们的完成又标志事件v5

2、、v6的发生。当活动a10、a11、a12完成后，整个计划完成。上述有向图存在唯一的入度为0的开始结点v1，表明整个计划从该事件开始；存在唯一的出度为0的完成结点vn，表明该事件完成后，整个计划结束。现在的问题是，整个计划完成至少需要多少时间，为提前完成计划应该加快哪些活动的速度。输入：输入： n(事件数，1n100) e(活动数，1e4000)。以下为e行，每行为连接两个事件的序号以及活动需要的时间输出：输出：完成整个计划的最少时间。以下k行，每行为一个关键活动（i，j）和目前花费的时间wij，加快该活动的速度能提前完成计划 关键路径的由来关键路径的由来如果有向图的结点表示活动，有向边表示活

3、动间的优先关系，那么我们通过拓扑排序将图中的结点排成一个满足活动先后顺序要求的线性序列。如果有向有权图满足下述条件存在唯一的入度为0的结点和唯一的出度为0的结点；可通过拓扑排序将图中的结点排成一个满足活动先后顺序要求的线性序列（即有向图没有回路）则称该有向有权图为AOV网（活动结点网络）。 利用AOV网可以估算出整个计划完成至少需要多少时间，为提前完成计划应该加快哪些活动的速度等问题。解决这些问题有一种有效的方法求关键路径方法。由于AOV网中的活动可以并行进行，因此完成整个计划的最少时间是从开始结点v1到完成结点vn的最长路径长度（路径上各边权的和）。具有最大长度的路径称作关键路径。在上图中v

4、1v2v5v8v9是一条关键路径，长度为18。换句话说，整个计划至少需要18个时间单位完成。关键路径上的活动又称关键活动。如果不能按期完成这些活动会贻误整个计划。找出关键活动后就可以适当调度，集中力量于关键活动，以保证计划如期或提前完成。关键路径的计算关键路径的计算为了找出关键活动，我们先定义几个变量： nAOV网的结点数； mAOV网的有向边数； eeivi事件可能发生的最早时间，即从开始结点v1至结点vi的最长路径长度。我们从ee(1)=0开始向前递推 eej=maxeei+wij|(i,j) E； lei在保证完成结点vn所代表的事件在een时刻发生的前提下，事件vi允许发生的最晚时 间

5、，即lei=ee(n)-vi至vn最长路径长度。我们从len=een出发向后递推 lei=minlej-wij |(i,j) E ek活动ak（对应边）可能的最早开始时间，即等于事件vi的可能的最早发生时间eei；lk活动ak(对应边)允许的最晚完成时间，即等于事件vj允许最晚发生时间lej； (1i， jn， 1km) 显然活动ak的最大可利用时间是lk-ek。若最大可利用时间等于ak边所带的权wk(即为计划时间)，则ak是关键活动。ak延期，则整个计划将顺延。若最大可利用时间大于wk，则ak不是关键活动，ak的完成时间允许超过wk。只要不超过最大可利用时间，无妨于整个计划完成的进度。我们可

6、以采取以下步骤，计算上面定义的几个变量值，从而找到关键活动： 计算能影响整个计划完成时间的关键活动计算能影响整个计划完成时间的关键活动 在找出关键活动后，只要将所有的非关键活动从AOV网中去掉，这时从开始结点至完成结点的所有路径都是关键路径。AOV网中的关键路径可能不止一条。并不是加快任一关键活动就可以缩短整个计划的完成时间。只有加快并不是加快任一关键活动就可以缩短整个计划的完成时间。只有加快那些包括在所有关键路径上的关键活动才能达到目的的。那些包括在所有关键路径上的关键活动才能达到目的的。设a为关键路径组成的01矩阵，a0为辅助矩阵；b为关键活动序列，其中bk.x、bk.y和bk.l分别为第

7、k项关键活动的两个顶点序号和花费；nopath为v1至vn间有路可走的标志； 首先计算关键活动序列b和关键活动组成的有向图a。然后逐一地在a图中去除一条关键活动边，看一看是否存在v1至vn的路径。如果v1至vn间无路可走,则说明这个关键活动为影响整个计划完成的关键活动。判别过程采用深度优先搜索procedure dfs(i:integer)；深度优先搜索a0图中由顶点i出发的所有可能路径。若存在一条到达顶点n的路径，则nopath设为false；否则为true begin fitrue； if i=n then begin nopathfalse；exit；endthen for j1 to

8、n do begin if (not(fj)and(a0i,j=1) then dfs(j)； end；for end；dfs由此得出算法 活动的时间矩阵w初始化为0；输入带权有向图的信息（顶点数n、活动数e和活动的时间矩阵w）；if 图中的所有顶点不能排成一个拓扑序列 then 失败退出；fillchar(ee，sizeof(ee)，0)；for i1 to n-1 do for j1 to n do 计算各个事件的最早发生时间表ee if (i,j)E)and(eejeei+wij) then eejeei+wij；输出完成整个计划的最少时间een；for i1 to n do leiee

9、n； 所有事件的最晚发生时间初始化k0； 关键活动数初始化for in-1 downto 1 do 计算各个事件的最晚发生时间表le for j1 to n do if (wij0)and(leieej-wij) then leieej-wij；fillchar(a,sizeof(a),0)； 由关键活动组成的有向图a初始化for i1 to n-1 do 计算关键活动和由关键活动组成的有向图a for j1 to n do if (wij0 )and(lej-eei=wij) then begin kk+1；bk.xi；bk.yj；bk.lwij；ai,j1；end；then for t1 to k do 枚举每一个关键活动Begina0a；a0bt.x，bt.y0；在有向图a中去除第t个关键活动fillchar(f，sizeof(f)，false)；nopathtrue；访问标志和成功标志初始化dfs(1)；通过深度优先搜索判断v1与vn间是否有路if nopath then输出关键活动（bt.x，bt.y）和目