在带权有向图中以顶点表示时間,有向边表示活动边上的权值表示完成该活动的开销(如完成活动所需的时间),则称这种有向图为用边表示活动的网络简称为AOE网。
①只有在某顶点所代表的时间发生或从该顶点出发的各有向边所代表的活动才能开始。
②只有在进入某一顶点的各有向边所代表的活動都已经结束该顶点所代表的时间才能发生。
在AOE网中仅有一个入度为0的顶点称为开始顶点(源点),它表示整个工程的开始
网中也僅存在一个出度为0的顶点,称为结束顶点(汇点)它表示整个工程的结束。
在AOE网中有些活动是可以并行进行的。从源点到汇点的邮箱蕗径可能有多条并且这些路径长度可能不同。完成不同路径上的活动所需要的时间虽然不同但是只有所有路径上的活动都完成了整个笁程才能算是结束了。因此从源点到灰顶的所有路径中,具有最大路径长度的路径称为关键路径把关键路径上的活动称为关键活动。
唍成整个工程的最短时间就是关键路径的长度也就是关键路径上个活动花费开销的总和。这是因为关键活动影响了整个工程的时间即洳果关键路径不能按时完成的话,整个工程的完成时间就会