|
活动网络
7.6.2 用边表示活动的网络AOE问题的提出相关定义求关键路径的方法邻接表代码实现效率分析
思考
7.6.2 用边表示活动的网络AOE
问题的提出
把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始。 【例】设一个工程有11项活动，9个事件事件。V1——表示整个工程开始事件，V9——表示整个工程结束。 问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？ 
相关定义
边表示活动 activity on edge,AOE 有向边表示一个工程中的各项活动，边上的权值表示活动持续的时间（duration）。 顶点表示事件（event），事件的发生说明在它之前的活动已完成，而在它之后的活动可以开始。源点：没有入边的点；汇点：没有出边的点。 一个工程可能有多个源点，但AOE网络中只能有一个源点和一个汇点。从源点到汇点可能有多条有向路径，路径上各活动所需时间之和叫该路径的路径长度。（路径上各活动持续时间之和）具有最大路径长度的路径叫做关键路径，上图的关键路径有a1，a4，a7，a10 和a1，a4，a8，a11，它们的路径长度均为18。关键路径上的所有活动都叫做关键活动，对上图的AOE，关键活动是a1，a4，a7，a8，a10，a11。 关键活动上持续时间的变化可能影响整个工程的工期。任意一个关键活动延迟，整个工期都会延迟；反之，任意一个关键活动缩短，整个工期会缩短。Ve(j)——表示事件Vj的最早发生时间，是从源点V0到顶点Vj的最长路径长度。Ve[j]决定了以顶点Vj为弧尾的弧所代表的活动可以开始的最早时间。Vl(j)——表示事件Vj的最迟发生时间，是工程按期完成情况下Vj的最迟允许开始时间。e(i)——表示活动ai的最早开始时间，设ai是在上，e[i]是从源点到Vk的最长路径长度，故e[i]=Ve[k]。l(i)——表示活动ai的最迟开始时间，是工程按期完成情况下ai的最迟允许开始时间。设ai在上，并且aj的持续时间为dur()，l[i]=Vl[j]-dur()。l(i)-e(i)——表示完成活动ai的时间余量（松弛时间）。是活动ai的最迟允许开始时间和最早可能开始时间之差（l[i]-e[i]）。关键活动——关键路径上的活动，即*l(i)=e(i)*的活动。
求关键路径的方法
求解AOE顶点的拓扑排序序列 （1）按拓扑序列次序，从V0开始求各事件的Ve[ i ] 求Ve[i]的递推公式：从Ve[0]-0开始，向前递推，Ve[ j ]=Max{ Ve[ i ] + dur() | ∈T }，j=1,2,……,n-1；其中，T是所有以顶点Vj为弧头的弧的集合。 （2）按逆拓扑序列次序，从Vn-1开始求各事件的Vl[ i ] 求Vl[i]的递推公式：从Vl[n-1]=Ve[n-1]开始，反向递推，Vl[ i ]=Min{ Vl[ j ]-dur() | ∈T }，i=0,1,2,……,n-2；其中，T是所有以顶点Vi为弧尾的弧的集合。 （3）设活动ak（k=1,2,…,e）对应带权有向边，它的持续时间用 dur() 表示，则有： e[k]=Ve[ i ]；l[k]=Vl[ j ]-dur() 。e[k]=l[k]的活动为关键活动。  计算关键路径的算法步骤 （1）输入n个顶点和e条带权的有向边，建立邻接表结构； （2）计算每个顶点的入度； （3）从源点V0出发，令Ve[0]=0，按拓扑有序的顺序计算每个顶点的Ve[ j ](j=1, 2, … n-1)。若拓扑排序中遍历的顶点数小于n，则说明网络中存在有向环，不能继续求关键路径。 （4）从汇点Vn-1出发，令Vl[n-1] = Ve[n-1]，按逆拓扑有序顺序求各顶点的Vl[ i ](i=0, 1, …, n-2) （5）根据各顶点Vi的Ve[ i ]和Vl[ i ]值，求各条弧ak的e[k]和l[k]。 （6）输出关键活动ak(e[k]= =l[k]即为关键活动)。
邻接表代码实现
template void StatInDegree(const AdjListDirGraph &g,int *InDegree)
{
for(int v=0;v
InDegree[v]=top;
top=v;
}
while(top!=-1)//栈非空
{
v=top;
top=InDegree[v];
g.GetElem(v,e);
cout |