【摘 要】 本文利用数据结构中求解关键路径的相关方法，解决了在实际工程项目的计划设计时，我们通常所关心的两个问题：整个工程的竣工最少需要多少时间；影向整个工程进度按时完工的主要子工程是哪些。
　　【中图分类号】 G6425 【文献标识码】 A 【文章编号】 2095-3089（2017）13-00-01
　　一、关键路径的基本概念
　　在数据结构中，如果我们用顶点表示事件的发生（比如：某项活动的开始或结束），用边表示活动（活动的实施），边所对应的权值表示活动所持续的时间代价，则称这样边带权的有向图为AOE（Activity on edge network）网。AOE网通常在工程或项目管理中有着实际的应用。
　　如果用AOE网来描述一项工程或项目实施计划的话，那么，边可以表示子工程或子活动，有向边（也称为弧）表示子工程實施的先后次序，边所带的权表示子工程实施的持续时间代价。我们在设计工程施工计划时，有时必须关心整个工程竣工最少需要多少时间；哪些子工程的施工进度会影响到整个工程的按时完工，如果加速这些子工程的施工进度能否提高整个工程的效率。因此，有必要对子工程的施工次序、子工程互相之间的影响关系、预计完成的时间有一个预测（估算），同时要确定影响整个工程进度的关键子工程有哪些。这就形成了工程施工的AOE网。
　　从数据结构中我们得知，AOE网是一个有向无环结构的图，AOE网应具有下面两个性质：
　　（1）只有在某一个顶点所表示的事件发生，其后的从该顶点出发的各个有向边所代表的活动才能开始进行。
　　（2）只有当指向某一顶点的所有边代表的活动全部结束时，该顶点所代表的事件才能发生。
　　并且，每一个AOE网中只能有一个顶点的入度（指向该顶点的边的条数）为0，称之为源点；每一个AOE网中也只能有一个出度（出自该顶点的边的条数）为0，称之为汇点。
　　二、关键路径在某工程管理中的应用
　　下面我们结合某工程项目的实施计划情况，介绍关键路径在计算整个工期以及确定重点子工程问题中的应用过程。某工程项目中共有15项子工程，每个子工经过估算的施工时间、前期子工程等情况见表1。
　　下面就数据结构中求解关键路径、关键活动（即子工程）的相关算法，简要介绍整个工程的竣工最少需要多少时间、影响整个工程进度的主要子工程有哪些。
　　1、计算方法
　　因为在同一工程项目中的一些子工程是可以同时施工的，所以，完成整个工程所需要的时间应该是从源点到汇点之间的最大路径长度（即该路径上所有子工程施工时间之和）。
　　在AOE网中求解关键路径的方法：
　　（1）计算事件最早发生的时间
　　设Ve[k]为第k个事件的最早发生时间，根据AOE网的性质，只有当第k个子工程的前期子工程全部结束时，第k个子工程才能开工，即第k个子工程的最早时间才能确定。而子工程的最早结束时间为ve[j]+dut（）。计算方法如下：
　　Ve[1]=0
　　Ve[k]=max{ve[j]+dut（）} 表示从第j个顶点到第k个顶点的一条边
　　（2）计算事件最晚发生的时间
　　设Vl[k]是在不影响整个工程按时完工的前提下，第k个事件的最晚开工时间；n为最后一个事件（本例中竣工发生的事件，亦即第11个事件）。计算方法如下：
　　Vl[n]=ve[n]
　　Vl[k]=min{vl[j]-dut（）}
　　（3）计算活动（即子工程）的最早开工时间
　　设e[i]为第i项活动（ai）的最早开始时间。活动在AOE网中对应着一条弧，用所表示的一项活动。依据AOE网的性质，只有事件vk发生了，活动ai才能开工。即，活动ai的最早开工时间应等于事件vk的最早发生时间。计算方法如下：
　　e[i]=ve[k]
　　（4）计算活动ai的最晚开始时间
　　设l[i]为活动ai的最晚开始时间。最晚开始时间是指在不影响整个工程按时完工的前提下，必须开工的最迟时间。计算方法如下：
　　l[i]=vl[j]-dut（）
　　根据上述方法和公式分别计算每个事件的最早、最晚发生时间（略）以及表1中各项子工程的最早、最晚开工时间（见表2）
　　2、确定关键路径与关键活动
　　根据AOE网求解关键路径及关键活动的算法可知：凡是最早开工时间与最晚开工时间相等的子工程即为关键活动（关键子工程），从上表中可以看出zgc2、zgc5、zgc9、zgc13、zgc14、zgc15等六项子工程是该工程项目中主要子工程，它们的施工情况直接影响着整个工程的施工进度。要想使整个工程按时竣工，就必须保正这六项子工程的施工进度按时进行，如果能够提高这六项子工程的施工效率，则可使得整个工程提前竣工。
　　根据AOE网求解关键路径的算法可知，从源点出发经过上述六个关键活动到达汇点，所形成的一条或多条路径即为关键路径（本例中只有一条），关键路径上所有活动持续时间的总和（最大）即为整个工程竣工所需要的最少时间，在本例中为4+3+4+4+1+6=22，也就是说，在本例所描述的工程项目中，整个工程竣工所需要的最少时间是22天。
　　三、结语
　　虽然说，关键子工程的施工效率直接影响着整个工程的按时完工，但是，其它子工程如果延期足够长也会影响整个工程的进度。所以，要保证工程进度，还是要全面管控所有子工程的实施。
　　另外，在预测每个子工程的施工时长时，要注意预测结果的准确性，否则，整個工程计划就不具合理性；同时更要注意每个子工程之间的接续关系，安排要紧凑、科学，才能保障整个工程项目的如期竣工。
　　参考文献：
　　郑诚.数据结构导论.外语教学与研究出版社.北京：2012
　　陈承欢.数据结构分析与应用实用教程.清华大学出版社.北京：2015