会计学7.5.2关键(guānjiàn)路径AOE-网上图AOE-网中：共有11项活动：a1,a2,a3,…a11；共有9个事件(shìjiàn)：v1,v2,v3,…v9，每个事件(shìjiàn)表示在它之前的活动已经完成，在它之后的活动可以开始。由于整个工程只有一个(yīɡè)开始点和一个(yīɡè)完成点，在正常的情况（无环）下，网中只有一个(yīɡè)入度为零的点（称作源点）和一个(yīɡè)出度为零的点（称作汇点）依据AOE-网可以(kěyǐ)研究什么问题？完成工程的最短时间是从源点到汇点的最长路径(lùjìng)的长度。路径(lùjìng)长度最长的路径(lùjìng)叫做关键路径(lùjìng)。从v1到v9的最长路径(lùjìng)是（v1,v2,v5,v8,v9），路径(lùjìng)长度是18。假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定(juédìng)了所有以vi为尾的弧所表示的活动的最早开始时间。用e(i)表示活动ai的最早开始时间。l(i)－e(i)两者之差意味着完成活动ai的时间余量。我们(wǒmen)把l(i)＝e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。由此可知：辨别关键活动就是找e(i)＝l(i)的活动。为求得AOE网中活动的e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。若活动ai由弧<i,j>表示(biǎoshì)，持续时间记为dut(<i,j>)，则有如下关系：活动i的最早开始时间等于事件j的最早发生时间e(i)＝ve(i)活动i的最迟开始时间等于事件k的最迟时间减去活动i的持续时间l(i)＝vl(j)-dut(<i，j>)求ve(j)和vl(j)需分两步进行：ve[j]和vl[j]可以采用(cǎiyòng)下面的递推公式计算：（1）向汇点递推ve(源点)=0；ve(j)=Max{ve(i)+dut(<i,j>)}（2）向源点递推由上一步的递推，最后总可求出汇点的最早发生时间ve[n]。因汇点就是结束(jiéshù)点，最迟发生时间与最早发生时间相同，即vl[n]=ve[n]。从汇点最迟发生现时间vl[n]开始，利用下面公式：vl(汇点)=ve(汇点);vl(i)=Min{vl(j)–dut(<i,j>)}由此得到下述求关键路径的算法：1）输入e条弧<i,j>，建立AOE网的存储(cúnchǔ)结构。2）从源点v0出发，令ve[0]＝0按拓扑有序求其余各顶点的最早发生时ve[i]（1≤i≤n-1）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。3）从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2≥i≥0)；4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。如上所述，计算顶点(dǐngdiǎn)的ve值是在拓扑排序的过程中进行的，需对拓扑排序的算法作如下修改：1）在拓扑排序之前设初值，令ve(i)=0（0<=i<n-1）;2）在算法中增加一个计算vi的直接后继vj的最早发生时间的操作：若ve(i)+dut(<i,j>)>ve(j),则ve(j)=ve(i)+dut(<i,j>)；3）为了能按逆拓扑有序序列的顺序计算各顶点(dǐngdiǎn)的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，则需要在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则在计算求得各顶点(dǐngdiǎn)的ve值之后，从栈顶至栈底便为逆拓扑有序序列。总之，关键路径的求解操作包括(bāokuò)：1）计算ve[j]和vl[j]①向汇点递推ve(源点)=0；ve(j)=Max{ve(i)+dut(<i,j>)}②向源点递推vl(汇点)=ve(汇点);vl(i)=Min{vl(j)–dut(<i,j>)}求最早发生(fāshēng)时间ve的算法求关键(guānjiàn)路径的算法例：求下图AOE网的关键(guānjiàn)路径顶点练习(liànxí)：求下图AOE网的关键路径/总结：有向无环图是描述(miáoshù)一项工程或系统的进行过程的有效工具。AOV网（顶点表示活动的有向网）与拓扑排序－－解决工程或系统能否顺利进行；AOE网（边表示活动的有向网）和关键路径问题－－估算整个工程完成所必须的最短时间，求解哪些活动为关键活动。第7章图7.1图的定义和术语7.2图的存储结构(jiég