事件vi的可能的最早发生时间earliest(i)：是从开始顶点v0到顶点vi的最长路径的长度。

 事件vi的允许的最迟发生时间latest(i)：是在不影响工期的条件下，事件vi允许的最晚发生时间，它等于earliest(n-1)减去从vi 到vn-1的最长路径的长度。

 设活动ak关联的边为<vi,vj>，持续时间记为w(i,j)

 活动ak可能的最早开始时间early(k)＝earliest(i)

 活动ak允许的最迟开始时间late(k)＝latest(j)-w(i,j)

算法实现：

以邻接表作存储结构；

从源点V0出发，令earliest[0]=0,按拓扑序列求各顶点的earliest[i]；

从汇点Vn-1出发，令latest[n-1]=earliest[n-1],按逆拓扑序列求其余各顶点的latest[i]；

若每条弧ak关联的边为<vi,vj>，根据各顶点的earliest和latest值，计算每条弧的early[k]=earliest(i)和late[k]=latest(j)-w(i,j),找出early[k]=late[k]的关键活动。

template<class T>
void ExtLGraph<T>::Earliest(int* earliest,int* order)
{   //求各顶点的earliest[i]
    for(int i=0;i<n;i++) earliest[i]=0;
     for(i=0;i<n;i++){
		  int k=order[i];
		  for (ENode<T>* p=a[k];p;p=p->nextArc)
		     if (earliest[p->adjVex]<earliest[k]+p->w) 
		     	  earliest[p->adjVex]=earliest[k]+p->w;
	 }
 }

template<class T>
void ExtLGraph<T >::Latest(int* latest,int* order,int longest)
{   //求各顶点的latest[i]
    for (int i=0;i<n;i++) latest[i]=longest;
    for (i=n-2;i>-1;i--){
        int j=order[i]; 
        for (ENode<T>* p=a[j];p;p=p->nextArc) 
		if (latest[j]>latest[p->adjVex]-p->w)
		    latest[j]=latest[p->adjVex]-p->w;
     }
 }

 注释：关键路径算法与拓扑排序有相同的时间复杂度，其时间复杂度为 O(n+e)。