点击进入>>>>>

  关键路径这个知识点在软件设计师考试中，是一个难点。

  说到关键路径这个概念，大家应该多少有些印象，可能都知道它是“最长路径”而不是“最短路径”，但说到它为什么是最长路径，提出这个概念的用意何在，它有什么应用，在计算机中关键路径是如何求的等问题却没有几个人能真正搞清楚，甚至书上给出了完整的例子，都有很多人看不懂。下面我先会简单的说明基本概念，然后以一个例子，结合平时希赛网学员的疑问，对这个知识点进行详细的分析。

  在AOV网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。例如，图1表示一个具有10个活动的某个工程的AOE网络。图中有7个顶点，分别表示事件1～7，其中1表示工程开始状态，7表示工程结束状态，边上的权表示完成该活动所需的时间。

　 下面我们来理解一下关键路径的思想，图1虽节点不多，但是为了让问题变得更为简单、直观，我们画另一个AOE网络，如图2所示。

　 从图2中我们可以看出，关键路路径实际上是从源点到目的地的最长路径。为什么是最长路径呢?因为图中的某些事件是可以并发执行的。如图2所示，当到达V1后，可以同时往V2，V3，V4三个方向走，而V2，V3，V4都有到Vk的路径，且长度都为1，并且Vk是终点，则关键路径是V1->V2->Vk。因为这条路径最长，只要这条路径到目的地Vk时其他的都已经到达Vk。而在这条关键路径上的活动a2，a5称为关键活动。

   为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量：
Ve(j)、Vl(j) ：顶点j事件最早、最迟发生时间。
e(i)、l(i)：活动i最早、最迟开始时间。
从源点V₁到某顶点Vj的最长路径长度称为事件Vj的最早发生时间，记为Ve(j)。Ve(j)也是以V_j为起点的出边<V_j，V_k>所表示的活动ai的最早开始时间e(i)。
在不推迟整个工程完成的前提下，一个事件V_j允许的最迟发生时间记为V_l(j)。显然，l(i) =V_l( j)-(a_i所需时间)，其中j为ai活动的终点。满足条件l(i) =e(i)的活动为关键活动。
求顶点Vj的Ve(j)和Vl(j)可按以下两步来做。
（1）由源点开始向汇点递推。

其中，E₁是网络中以Vj为终点的入边集合。
（2）由汇点开始向源点递推。

其中，E₂是网络中以Vj为起点的出边集合。

   相关推荐：

   希赛软件设计师题库

   软件设计师考试必看如何应考？

   2015年下半年软件设计师考试报名指南

   软件设计师级考试大纲（2004年新版）