|
|
|
在有向图中，顶点表示事件，有向边表示活动，边上的权表示活动的持续时间，此有向图G称为边表示活动的网络，简称为AOE网（Activity On Edge）。其中，每个事件表示在它之前的活动已经完成，在它之后的事件可以开始。整个工程的开始点（入度为0）称为源点，一个完成点（出度为0）称为汇点。
|
|
|
|
关键路径是从源点到汇点之间路径长度最长的路径，它是完成工程的最短时间。路径长度是指路径上各活动的持续时间之和。
|
|
|
|
最早发生时间表示从源点V1到Vi的最长路径长度。最迟开始时间是指在不推迟整个工程完成的前提下，活动ai必须最迟开始进行的时间l(i)，活动ai必须最早开始进行的时间为e(i)。l(i)-e(i)为完成活动ai的时间余量，将l(i)=e(i)的活动叫作关键活动。
|
|
|
|
|
|
（1）从Ve(j)=0开始向前递推：Ve(j)=Max{Ve(i)+dut()},∈T, j=1,2,…,n, T是以j为头的弧的集合。
|
|
|
|
（2）从V1(n)=Ve(n)起向后递推：V1(i)=Min{V1(j)-dut()},∈S, i=n-1, …, 1, S是以i为尾的弧的集合。
|
|
|
|
|
|
（1）输入e条弧，并建立AOE网的十字链表存储结构。
|
|
|
|
（2）从源点出发，令Ve[0]=0，按拓扑排序求每个顶点的最早发生时间Ve(i)(1≤i≤n)。若拓扑排序的循环次数小于n，则说明网中存在回路，不能求关键路径。
|
|
|
|
（3）从汇点Vn出发，令V1[n-1]=Ve[n-1]，按逆拓扑排序求每个顶点的最迟发生时间V1(i)(2≤i≤n-2)。
|
|
|
|
（4）根据各顶点的Ve和V1值，校正每条弧S的最大开始时间e(s)和最迟开始时间l(s)；若e(s)=1(s)，则该弧为关键活动，输出。
|
|
|
