事件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)。