关键路径

2014/12/23 12:54 PM posted in 算法&数据结构

AOE网

与AOV网相对应的是AOE网，即边表示活动的网。AOE网是一个带权的有向无环图，其中，定点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE网可以用来估算工程的完成时间。

关键路径

设一个工程有11项活动，9个事件，事件 V1表示整个工程开始，事件V9——表示整个工程结束，问题：

完成整项工程至少需要多少时间？
哪些活动是影响工程进度的关键？

关键路径的几个术语

路径长度：路径上各活动持续时间之和。
关键路径：路径长度最长的路径。
关键活动：关键路径上的活动，即这些活动的时间延迟或提前会影响整个工程工期的延迟或提前。

我们可以说，我们可以对一个工程计划，先从头开始保证每个任务尽快完成，那么就可以计算出每个点的最短完成时间。

如果我们从尾开始，以尾的最快完成时间为期限，再逆推每个点最迟完成时间且保证不耽误尾节点的完成，那么就可以计算出每个点的最晚完成时间。

那么一个节点完成时间是在最早完成时间到最晚完成时间的区间内则不会影响整个工程的进度，如果一个节点最早完成时间和最晚完成时间相同，就意味着，如果这个节点延误了，整个工程将被延误。那么，这就是关键活动。

换句话，如果找到关键活动，如果加快关键活动的完成，整个工程将更快完成。

Ve(j)：表示事件Vj的最早发生时间。

Vl(j)：表示事件Vj的最迟发生时间。

e(i)：表示活动ai的最早开始时间。

l(i)：表示活动ai的最迟开始时间。

l(i)-e(i)：表示完成活动ai的时间余量。

若时间余量为0，则该活动为关键活动，所在的路径为关键路径。

设活动ai用弧表示，其持续时间记为：dut() 则有：

e(i)=Ve(j)
l(i)=Vl(k)-dut()

求Ve（j）和Vl（j）需分两步进行：

从Ve（0）=0开始向前推进：Ve（j）=Max{Ve（i） + dut（）（每条指向j的边）}
从Vl（n-1）=Ve（n-1）起向后推进：Vl（i）=Min{Vl（j）-dut（）（每条指向j的边）}

这样，就能找到每个关键活动。

因此，可以提炼算法：

输入e条弧建立AOE网的存储结构
从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中各顶点数n，则说明网中存在环，不能求关键路径，算法终止，否者执行第3步
从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]
根据各顶点的ve和vl值，求每条弧s的最早开始时间e（s）和最迟开始时间l（s）。若某条弧满足e（s）=l（s），则为关键活动

伪代码：

Status TopologicalOrder(ALGraph G, Stack &T) {
  // 有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。
  // T为拓扑序列定点栈，S为零入度顶点栈。
  // 若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR。
  Stack S;int count=0,k;
  char indegree[40];
  ArcNode *p;
  InitStack(S);
  FindInDegree(G, indegree);  // 对各顶点求入度indegree[0..vernum-1]
  for (int j=0; jnextarc) {
      k = p->adjvex;            // 对j号顶点的每个邻接点的入度减1
      if (--indegree[k] == 0) Push(S, k);   // 若入度减为0，则入栈
      if (ve[j]+p->info > ve[k])  ve[k] = ve[j]+p->info;
    }//for  *(p->info)=dut()
  }//while
  if (countnextarc) {
      k=p->adjvex;  dut=p->info;     //dut
      if (vl[k]-dut nextarc) {
      k=p->adjvex;dut=p->info;
      ee = ve[j];  el = vl[k]-dut;
      tag = (ee==el) ? '*' : ' ';
      printf(j, k, dut, ee, el, tag);   // 输出关键活动
    }
  return OK;
} // CriticalPath