|
在有向图中,顶点表示事件,有向边表示活动,边上的权表示活动的持续时间,此有向图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),则该弧为关键活动,输出。
|
|
|