2019年农信社招聘最新备考考点——关键路径

 1.基本概念

关键路径是解决工程完成需要的最短时间问题。

AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网称为AOE网(Activity On Edge Net-work)。AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。

关键路径：AOE网路径上各个活动所持续的时间之和称为路径长度，从源点到终点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

2.关键路径的算法

①建立AOE网的存储结构;

②从源点出发，令ve[0]=0，然后求出其余各顶点的最早发生时间ve[i](1<=i<=n-1)。即从前向后计算，取最大的值，计算方法是，直接前驱结点的ve[j]+到达边(指向顶点的边)的权值，有多个值的取较大的。

③从终点

出发，令vl[n-1]=ve[n-1]，然后求其余各顶点的最迟发生时间vl[i](2<=i<=n-2)。即从后向前计算，取小值，也就是，直接后继结点的vl[j] -发出边(从顶点发出的边)的权值，有多个值的取较小者。

④根据各点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。其中，活动的最早开始时间等于它的发出顶点的最早发生时间，活动的最迟开始时间为活动的到达顶点的最晚发生时间减去边的权值。若满足条件l(i)=e(i)，则为关键活动。

⑤计算AOE网的关键路径

AOE网即边表示活动的网络。通常，可用AOE网来估算工程计划的完成时间。如下所示的AOE网包括11项活动，9个事件，每个事件都有所需的完成时间。我们现在要解决的是：(1)完成整项工程至少需要多少时间(最短时间);(2)哪些活动是影响工程进度的关键(关键活动)。