精华内容
下载资源
问答
  • 关键路径的算法演示过程,用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网。
  • 图解:什么是关键路径

    万次阅读 多人点赞 2020-05-06 20:31:39
    小禹禹,五一假期马上结束了,你们过得怎么样呢?有没有玩得很开心,收获满满呢?好想听你们在评论区说一说。哈哈,不过我们还是先来说一说今日景禹要给你们分享的内容,关键路径。何为关键路径?如果...

    小禹禹,五一假期马上结束了,你们过得怎么样呢?有没有玩得很开心,收获满满呢?好想听你们在评论区说一说。哈哈,不过我们还是先来说一说今日景禹要给你们分享的内容,关键路径。何为关键路径?如果在一个有向无环图中求得关键路径?关键路径又有什么作用呢?且听景禹慢慢道来。

    前言

    昨日景禹在写拓扑排序的时候提到,拓扑排序是关键路径的基础,那么为什么这么说呢?相信小禹禹看完文章定能有所感悟。在此之前我们看一些简单但很重要的概念。

    什么是AOE网?

    AOE网(Activity On Edge)即边表示活动的网,是与AOV网(顶点表示活动)相对应的一个概念。而拓扑排序恰恰就是在AOV网上进行的,这是拓扑排序与关键路径最直观的联系。AOE网是一个带权的有向无环图,其中顶点表示事件(Event),弧表示活动,权表示活动持续的时间。(小禹禹心想,这不就等于没说吗?看过后就没了印象)。景禹给大家备好了图,下面的就是一个AOV网:

    其中 表示事件, 表示活动,活动的取值表示完成该活动所需要的时间,如 表示完成活动 所需要的时间为6天。此外,每一事件   表示在它之前的活动已经完成,在它之后的活动可以开始,如   表示活动 已经完成,活动 可以开始了。

    什么是AOE网的源点和汇点?

    由于一个工程中只有一个开始点和一个完成点,故将AOE网中入度为零的点称为源点,将出度为零的点称为汇点。

    打个比方,我们现在有一个工程,就是将大象装进冰箱,那么源点就相当于我们现在接到这样一个任务,而汇点则表示我们完成了这个任务。那么我们之前所讲的打开冰箱门,将大象装进去,关上冰箱门就属于活动本身(即  所表示的信息),打开冰箱门所需要的时间就是活动所需要的时间,而完成某一个活动所到达的顶点就表示一个事件(冰箱门打开)。下图中的红色顶点 表示源点,  表示汇点。

    什么是关键路径呢?

    举个栗子。

    唐僧师徒从长安出发去西天取经,佛祖规定只有四人一起到达西天方能取得真经。假如师徒四人分别从长安出发,走不同的路去西天:孙悟空一个筋斗云十万八千里,一盏茶的功夫就到了;八戒和沙和尚稍慢点也就一天左右的时间;而唐僧最慢需要14年左右。徒弟到达后是要等着师傅的。那么用时最长的唐僧所走的路,就是取经任务中的关键路径。其他人走的路径属于非关键路径。

    由于AOE网中的有些活动是可以并行进行的(如活动 就是可以并行进行的),所以完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径就叫做 关键路径(Critical Path)。如下图中红色顶点和有向边构成的就是一条关键路径,关键路径的长度就是完成活动  和 所需要的时间总和,即为 6+1+9+2 = 18.

    我向小禹禹现在对于关键路径、源点、汇点、事件、活动和AOE网有了一个清晰的认识,但我们要想在一个有向图当中找到这样一条关键路径还得清楚下面的四个概念。

    小禹禹:我的天,一个关键路径光概念就这么多,还好景禹讲得清楚,不然我早跪了。

    景禹:哈哈,因为关键路径有用呀,她难免身加很多 “光环” ,小禹禹看完文章一定会佩服自己并感慨关键路径的,我们一起来看四个重要的概念呗!

    什么是ETV?

    ETV(Earliest Time Of Vertex):事件最早发生时间,就是顶点的最早发生时间;(看图说话)

    事件 的最早发生时间表示从源点 出发到达顶点 经过的路径上的权值之和,从源点 出发到达顶点 只经过了权值为6的边,则 的最早发生时间为6,表示在活动 完成之后,事件 才可以开始;同理,事件 要发生(即最早发生)需要活动 和活动 完成之后才可以,故事件   的最早发生时间为 5 + 2 = 7。其他顶点(事件)的最早发生时间同理可的。需要说明,事件的最早发生时间一定是从源点到该顶点进行计算的。

    什么是LTV?

    LTVLatest Time Of Vertex):事件最晚发生时间,就是每个顶点对应的事件最晚需要开始的时间,如果超出此时间将会延误整个工期。

    前面景禹在谈关键路径的概念时给出了一条上图中的关键路径,该关键路径( )的长度为18,为什么要提这个长度呢,因为要计算某一个事件的最晚发生时间,我们需要从汇点 进行倒推。计算顶点 的最晚发生时间为例,已知关键路径的长度为18,事件 到汇点 所需要的时间为 1 + 9 + 2 = 12,则事件 的最晚发生时间为18-12 = 6,聪明的小禹禹一定发现,这和事件 的最早发生时间不是一样吗?的确如此,对于关键路径上的顶点都满足最早发生时间 etv 等于 最晚发生时间 ltv 的情况,这也是我们识别关键活动的关键所在。再来计算一下事件 的最晚发生时间,事件 到汇点 所需要的时间为 4 + 4 = 8,则事件 的最晚发生时间为 18 - 8 = 10;相当于说活动 完成之后,大可以休息 3天,再去完成活动 也不会影响整个工期。

    什么是ETE?

    ETE(Earliest Time Of Edge):活动的最早开工时间,就是弧的最早发生时间。

    活动 要最早开工时间为事件 的最早发生时间 6;同理,活动 的最早发生时间为事件 的最早发生时间 7。显然活动的最早开工时间就是活动发生前的事件的最早开始时间。

    什么是LTE?

    LTE(Lastest Time of Edge):活动的最晚发生时间,就是不推迟工期的最晚开工时间。

    活动的最晚发生时间则是基于事件的最晚发生时间。比如活动 的最晚发生时间为事件 的最晚发生时间减去完成活动 所需时间,即 7 - 1 = 6;活动    的最晚发生时间为事件 的最晚发生时间减去完成活动 所需时间,即 14 - 4 = 10;

    从上面也就可以看出 只要知道了每一个事件(顶点)的ETV 和 LTV,就可以推断出对应的 ETE 和 LTE .  此外还需要注意,关键路径是活动的集合,而不是事件的集合,所以当我们求得 ETV 和 LTV 之后,还需要计算 ETE 和 LTE  。

    关键路径算法

    求关键路径的过程事实上最重要的就是上面提到的四个概念,ETV、LTV、ETE 和 LTE,求得了ETE与LTE之后只需要判断两者是否相等,如果相等则为关键路径中的一条边,则输出。为了清晰的明白算法的执行流程,我们一起 Step By Step.

    首先求事件的最早发生事件ETV,这里使用的就是之前分享的拓扑排序,我们也走一遍,算是对拓扑排序的回顾。不清楚的小禹禹可以回头看看之前的文章 图解:什么是拓扑排序?

    第一步,建立图所对应的邻接表。

    拓扑排序获得每一个事件的最早发生时间

    初始时将ETV当中的数据都设置为0:

    下面开始便是拓扑排序的过程了。

    第二步:将入度为零的顶点 入栈;

    第三步:顶点 出栈,并遍历顶点 的邻接顶点 ,即 index 分别为 1,2,3 的顶点 和顶点 ,并将邻接顶点的入度减1,判断是否为 0 ,如果为 0 则入栈。首先遍历 index = 1 顶点 ,并将顶点 的入度减 1 ,发现为零,则将顶点 入栈, 判断 ETV[0] + w( )  是否大于 ETV[1] , 发现大于,则将 ETV[1] 更新为 ETV[0] + w( )  =  6;同理遍历 index = 2 的顶点   ,将顶点 入栈,并将 ETV[2] 更新为 4 ;遍历 index = 3 的顶点   ,将顶点  入栈,并将 ETV[3] 更新为 5 。

    第四步:弹出栈顶元素 并遍历顶点 的邻接顶点 . 将顶点 的入度减一,并将 ETV[5] 更新为 ETV[3] + ,即为7.

    第五步:弹出栈顶元素 并遍历邻接顶点 .

    第六步:弹出栈顶元素 ,并遍历    的邻接顶点 .

    第七步:弹出栈顶元素 ,并遍历    的邻接顶点 .

    第八步:弹出栈顶元素 ,并遍历    的邻接顶点 .

    第九步:弹出栈顶元素 ,并遍历 的邻接顶点

    第十步:弹出栈顶元素 ,并遍历 的邻接顶点

    第十一步:将栈顶元素 出栈。

    其中,我们将拓扑排序过程中的出栈序列依次入栈,即拓扑排序结束时,我们响应的保存了一个出栈序列,用于逆向计算事件的最晚发生时间:

    根据事件的最早发生时间ETV推断事件的最晚发生时间 LTV

    通过拓扑排序我们获得了每一个顶点的最早发生时间 ETV,紧接着便可以计算 LTV了。

    计算LTV的值,即每一个顶点的最晚发生时间值,初始时将LTV的值初始化为汇点 的时间 18 。

    紧接着则是访问之前的出栈序列栈 。

    首先将顶点 出栈,什么都不做。

    第二步:将顶点 出栈,并判断LTV[6] 与 LTV[8] -  的大小,将 LTV 更新为 LTV[8] -  = 16

    第三步:将顶点 出栈,更新 LTV[7] 为 LTV[8] -  = 14。

    第三步:将顶点 出栈,并遍历 的邻接顶点  和 。用邻接顶点 的LTV值减去 活动 的值,并与顶点 的LTV值进行比较,将LTV[4] 更新为 7;同理用邻接顶点 的LTV值减去活动 的值,并与顶点 的值进行比较,发现相等不做更新。

    第四步,弹出栈顶元素 ,并遍历 的邻接顶点 , 用顶点 的LTV(最晚发生时间) 减去活动 所需时间,即为6,将顶点 的LTV[1] 更新为6.

    第五步,弹出栈顶事件(顶点) ,并更新顶点 的最晚发生时间。

    第六步:弹出栈顶事件(顶点) .

    第七步:弹出栈顶元素 并更新其最晚发生时间。

    第八步:弹出栈顶元素 并更新其最晚发生时间。使用事件 的最晚发生时间 6 减去活动 所需时间6 等于0,与顶点 的最晚时间相比较并更新为0。需要说明,事实上源点 的最晚发生时间与最早发生时间都为0,毋庸置疑

    此时我们得到每个事件(顶点)的最早发生时间和最晚发生时间,但 关键路径是活动的集合,所以接下来我们用事件的最早发生时间和最晚发生时间计算出活动(弧)的最早与最晚发生时间即可

    计算活动的最早与最晚发生时间

    第一步:从源点 开始,遍历源点的邻接顶点 ,  将弧 < > 上的活动 的最早发生时间更新为源点 的最早发生时间 0,将活动 的最晚发生时间更新为事件 的最晚发生时间 6 减去 活动 所需要的时间6,即为0. 判断活动 的最早发生时间与最晚发生时间是否相等,如果相等则为关键活动,并输出。同理遍历源点 的邻接顶点 ,并更新弧 的最晚发生时间与最早发生时间。

    第二步:访问顶点 ,遍历 的邻接顶点 . 将活动 的最早发生时间更新为 事件 的最早发生时间,将活动 的最晚发生时间更新为事件 的最晚发生时间 7 减去活动 所需时间 1,即为6.

    第三步:访问顶点 ,遍历 的邻接顶点 . 将活动 的最早发生时间更新为事件 的最早发生时间 4 ,将活动 的最晚发生时间更新为事件 的最晚发生时间 7 减去活动 所需时间 1,即为6.

    第四步:访问顶点 ,遍历该顶点的邻接顶点 , 将活动 的最早发生时间更新为事件 的最早发生时间5,活动 的最晚发生时间为事件 的最晚发生时间10 减去 活动  所需要的时间 2,即为8.

    第五步:访问顶点 ,并分别遍历该顶点的邻接顶点 和顶点 。将活动 的最早发生时间更新为时间 的最早发生时间7,最晚发生时间也更新为7。

    第六步:访问顶点 ,并遍历该顶点的邻接顶点 ,将活动 的最早发生时间更新为事件 的最早发生时间7,最晚发生时间更新为事件 的最晚发生时间 14 减去活动 所需时间4 ,即为10.

    第七步:访问顶点 ,更新活动 的最早发生时间和最晚发生时间。

    第八步:访问顶点 ,更新活动 的最早发生时间和最晚发生时间。

    第九步:访问顶点 ,没有邻接顶点,什么都不做。

    这样我们获得一个带权有向无环图中的关键路径:

    接下来我们再看完整的代码,我相信小禹禹必定会了然于胸(如果还不懂,建议多点儿耐心,多看几遍景禹辛苦给小禹禹写的分析)。

    // 边表结点声明
    typedef struct EdgeNode
    {
      int adjvex;
      struct EdgeNode *next;
    }EdgeNode;
    
    // 顶点表结点声明
    typedef struct VertexNode
    {
      int in; // 顶点入度
      int data;
      EdgeNode *firstedge;
    }VertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
      AdjList adjList;
      int numVertexes, numEdges;
    }graphAdjList, *GraphAdjList;
    
    int *etv, *ltv;
    int *stack2; // 用于存储拓扑序列的栈
    int top2; // 用于stack2的栈顶指针
    
    // 拓扑排序算法
    // 若GL无回路,则输出拓扑排序序列并返回OK,否则返回ERROR
    Status TopologicalSort(GraphAdjList GL)
    {
      EdgeNode *e;
      int i, k, gettop;
      int top = 0; // 用于栈指针下标索引
      int count = 0; // 用于统计输出顶点的个数
      int *stack; // 用于存储入度为0的顶点
      
      stack = (int *)malloc(GL->numVertexes * sizeof(int));
      
      for( i=0; i < GL->numVertexes; i++ )
      {
        if( 0 == GL->adjList[i].in )
        {
          stack[++top] = i; // 将度为0的顶点下标入栈
        }
      }
      
      // 初始化etv都为0
      top2 = 0;
      etv = (int *)malloc(GL->numVertexes*sizeof(int));
      for( i=0; i < GL->numVertexes; i++ )
      {
        etv[i] = 0;
      }
      stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
      
      while( 0 != top )
      {
        gettop = stack[top--]; // 出栈
        // printf("%d -> ", GL->adjList[gettop].data);
        stack2[++top2] = gettop; // 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
        count++;
        
        for( e=GL->adjList[gettop].firstedge; e; e=e->next )
        {
          k = e->adjvex;
          // 注意要点!
          // 将k号顶点邻接点的入度-1,因为他的前驱:下边这个if条件是分析整个程序的已经消除
          // 接着判断-1后入度是否为0,如果为0则也入栈
          if( !(--GL->adjList[k].in) )
          {
            stack[++top] = k;
          }
          
          if( (etv[gettop]+e->weight) > etv[k] )
          {
            etv[k] = etv[gettop] + e->weight;
          }
        }
      }
      
      if( count < GL->numVertexes ) // 如果count小于顶点数,说明存在环
      {
        return ERROR;
      }
      else
      {
        return OK;
      }
    }
    
    // 求关键路径,GL为有向图,输出GL的各项关键活动
    void CriticalPath(GraphAdjList GL)
    {
      EdgeNode *e;
      int i, gettop, k, j;
      int ete, lte;
      
      // 调用改进后的拓扑排序,求出etv和stack2的值
      TopologicalSort(GL);
      
      // 初始化ltv都为汇点的时间
      ltv = (int *)malloc(GL->numVertexes*sizeof(int));
      for( i=0; i < GL->numVertexes; i++ )
      {
        ltv[i] = etv[GL->numVertexes-1];
      }
      
      // 从汇点倒过来逐个计算ltv
      while( 0 != top2 )
      {
        gettop = stack2[top2--]; // 注意,第一个出栈是汇点
        for( e=GL->adjList[gettop].firstedge; e; e=e->next )
        {
          k = e->adjvex;
          if( (ltv[k] - e->weight) < ltv[gettop] )
          {
            ltv[gettop] = ltv[k] - e->weight;
          }
        }
      }
      
      // 通过etv和ltv求ete和lte
      for( j=0; j < GL->numVertexes; j++ )
      {
        for( e=GL->adjList[j].firstedge; e; e=e->next )
        {
          k = e->adjvex;
          ete = etv[j];
          lte = ltv[k] - e->weight;
          
          if( ete == lte )
          {
            printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
          }
        }
      }
    }

    时间复杂度分析

    假设图中的顶点个数为 ,边的数目为 。计算事件(顶点)的最早发生时间需要执行拓扑排序,时间复杂度为 。计算事件的最晚发生时间需要根据顶点的最早发生时间进行逆向扫描(也就是从终点向汇点的方向)需要 的时间复杂度。计算弧上活动的最早开始时间和最晚开始时间的时间复杂度为 ,所以总的求关键路径的时间复杂度为

    关键路径的应用

    (1) 完成整个工程至少需要多少时间;

    (2) 哪些活动是影响工程的关键。

    1956年,美国杜邦公司提出关键路径法,并于1957年首先用于1000万美元化工厂建设,工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中,节省了100万美元。

    说的更现实一点儿,以后大家如果要考PMP,那更是必须学会的算法了,有一天你成为了一个项目组组长,或者一个公司的老总,或者一个工程师,那么你就知道如何安排工程,知道什么是重点要关注的,知道如何进行资源配置。

    向关键路径要时间,向非关键路径要资源

    项目关键工作和关键路径的确定帮助项目经理抓住了项目工期管理中的主要矛盾,对于关键活动,优先安排资源,挖掘潜力,采取相应措施,尽量压缩需要的时间。而对非关键路径的各个活动,只要在不影响工程完工时间的条件下,抽出适当的人力、物力和财力等资源,用在关键路径上,以达到缩短工程工期,合理利用资源等目的。

    对不可控的任务,可采取办法规避安排在关键路径上面

    关键路径要提前发现风险,前期采取必要的措施规避掉

    关键路径是动态的,非关键路径有可能变成关键路径,所以项目过程中也要随时注意非关键路径的状况

    总结

    关键路径的查找过程中主要涉及四个概念,事件(顶点)的最早发生时间ETV,事件(顶点)的最晚发生时间LTV,活动(弧)的最早发生时间ETE,活动(弧)的最晚发生时间为LTE,其中事件的最早发生时间通过拓扑排序获得,而事件的最晚发生时间是通过逆向访问顶点(从源点到汇点的方向)结合最早发生时间获得,弧的活动的最早与最晚发生时间则是通过遍历一遍所有的弧结合事件的最早与最晚发生时间获得。关键路径在实际工程中应用广泛,如果你懂了,可以提高工程的工作效率,也可以适当地偷懒,哈哈,景禹就写到这里,这也是关于图的算法中的最后一个,希望小禹禹有所收获!

    记得分享给周围的小伙伴奥,点个文末的在看,谢谢小禹禹,祝你们学习愉快,每天都进步。也感谢每一天看我文章的小禹禹,特别开心,当你们给我鼓励的时候,有时候你会觉得自己做这件事情的意义,但后来我才知道意义也许就在于让更多的小禹禹对每一个算法都深入理解,然后回馈给我的赞美,不过景禹马上硕士毕业答辩,之后更新文章的频率可能会略有降低,但我绝不放弃,因为小禹禹,谢谢你们!文章可能略微长了点儿,小禹禹多点儿耐心好好看,一定会有所收获的,你要想,景禹能花那么多时间给小禹禹写文章,我难道不能花一个小时认真彻底学会一个算法?答案是肯定的,我坚信关注并鼓励景禹的每一位小禹禹都会越来越优秀,一起加油!

    推荐文章

    作者:景禹,一个追求极致的共享主义者,想带你一起拥有更美好的生活,化作你的一把伞。

    展开全文
  • 关键路径详解

    千次阅读 2019-11-22 15:46:36
    顶点活动(Activity On Vertex,AOV)网是用顶点表示活动,而用边集表示活动间优先关系的有向图。例如图10-57的先导课程示意图就是AOV网,其中图的顶点表示各项课程,也就是“活动”;有向边表示课程的先导关系,...

    AOV网:

    顶点活动(Activity On VertexAOV)网是指用顶点表示活动,而用边集表示活动间优先关系的有向图。例如图10-57的先导课程示意图就是AOV网,其中图的顶点表示各项课程,也就是“活动”;有向边表示课程的先导关系,也就是“活动间的优先关系”。显然,图中不应当存在有向环,否则会让优先关系出现逻辑错误。

    AOE网:

     

    边活动(Activity On EdgeAOE)网是指用带权的边集表示活动,而用顶点表示事件的有向图,其中边权表示完成活动需要的时间。例如图10-59中,边a1~a6表示需要学习的课程,也就是“活动”,边权表示课程学习需要消耗的时间;顶点V1~V6。表示到此刻为止前面的课程已经学完,后面的课程可以开始学习,也就是“事件”(如V5表示a4计算方法和a3实变函数已经学完,a6泛函分析可以开始学习。从另一个角度来看,a6只有当a4a5都完成时才能开始进行,因此当a4计算方法学习完毕后必须等待a5实变函数学习完成后才能进入到a6泛函分析的学习),显然“事件”仅代表一个中介状态。

    源点:AOE网中,没有入边的顶点称为源点;如顶点V1

     

    终点:在AOE网中,没有出边的顶点称为终点;如顶点V6

     

    AOE网的性质:

    ·只有在进入某顶点的活动都已经结束,该顶点所代表的事件才发生;

    ·只有在某顶点所代表的事件发生后,从该顶点出发的各活动才开始;

    AOE网中的最长路径被称为关键路径(强调:关键路径就是AOE网的最长路径),而把关键路径上的活动称为关键活动,显然关键活动会影响整个工程的进度。

    关键概念:

    1.事件的最早发生时间ve[k]earliest time of vertex):即顶点vk的最早发生时间。

    从源点向终点方向计算

    ve[0] = 0

    ve[1] = ve[0] + a0 = 0 + 4 = 4

    ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 = 6

    ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10

     

    2.事件的最晚发生时间vl[k]latest time of vertex):即顶点vk的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。

    从终点向源点方向计算

    vl[3] = ve[3] = 10

    vl[2] = vl[3] - a3 = 10 - 4 = 6

    vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4//之所以求最小,保证其他的点的最晚发生时间

    vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0 

     

    3.活动的最早开工时间e[k]earliest time of edge):即ax的最早发生时间。

    5条边,5个活动

    e[0] = ve[0] = 0

    e[1] = ve[0] = 0

    e[2] = ve[1] = 4

    e[3] = ve[2] = 6

    e[4] = ve[1] = 4

     

    4.活动的最晚开工时间l[k]latest time of edge):即ak的最晚发生时间,也就是不推迟工期的最晚开工时间。

    e[0] = v[1] - a0 = 4 - 4 = 0

    e[1] = vl[2] - a1 = 6 - 3 = 3

    e[2] = vl[2] - a2 = 6 - 2 = 4

    e[3] = vl[3] - a3 = 10 - 4 = 6

    e[4] = vl[3] - a4 = 10 - 6 = 4

     

    活动的最早开始时间最晚开始时间等,则说明该活动时属于关键路径上的活动,即关键活动

    算法设计:

    关键路径算法是一种典型的动态规划法,设图G=(V, E)是个AOE网,结点编号为1,2,...,n,其中结点1n 分别为始点和终点,ak=<i, j>EG的一个活动。算法关键是确定活动的最早发生时间ve[k]最晚发生时间vl[k],进而获取顶点的最早开始时间e[k]和最晚开始时间l[k]

    根据前面给出的定义,可推出活动的最早及最晚发生时间的计算方法:

    e(k) = ve(i)

    l(k) = vl(j) - len(i,j)

    结点的最早发生时间的计算,需按拓扑次序递推:

    ve(1) = 0

    ve(j) = MAX{ etv(i)+len(i, j) }

     

    对所有<i,j> Ei  结点的最晚发生时间的计算,需按逆拓扑次序递推:

    vl(n) = ve(n)

    vl(i) = MIN{vl(j) - len(i, j)} 对所有<i,j>E的j

     

    这种计算方法, 依赖于拓扑排序, 即计算ve( j) 前,应已求得j 的各前趋结点的ve值,而计算vl(i)前,应已求得i的各后继结点的vl值。ve的计算可在拓扑排序过程中进行,即在每输出一个结点i后,在删除i的每个出边<i,j>(即入度减1)的同时,执行

    if ( ve[i]+len(i,j)) > ve[j] )

    ve[j] = ve[i] + len(i,j)

     

    这时会发现,如果想要获得ve[j]的正确值,ve[il]~ve[ik]必须已经得到。有什么办法能够在访问某个结点时保证它的前驱结点都已经访问完毕呢?没错,使用拓扑排序就可以办到。

    当按照拓扑序列计算ve数组时,总是能保证计算ve[i]的时候ve[il]~ve[ik]都已经得到。但是这时又碰到另一个问题,通过前驱结点去寻找所有后继结点很容易,但是通过后继结点V;去寻找它的前驱结点V1~Vx似乎没有那么直观。一个比较好的办法是,在拓扑排序访问到某个结点时,不是让它去找前驱结点来更新ve[i],而是使用ve[i]去更新其所有后继结点的ve。通过这个方法,可以让拓扑排序访问到V;的时候,V1~Vk一定都已经用来更新过ve[i],此时的ve[i]便是正确值,就可以用它去更新V;的所有后继结点的ve值。

    //拓扑序列
    
    stack<int>topOrder;
    
    //拓扑排序,顺便求ve数组
    
    bool topologicalSort()
    
    {
    
        queue<int>q;
    
        for(int i=0;i<n;i++)
    
            if(inDegree[i]==0)
    
                q.push(i);
    
        while(!q.empty())
    
        {
    
            int u=q.front();
    
            q.pop();
    
            topOrder.push(u);//将u加入拓扑序列
    
            for(int i=0;i<G[u].size();i++)
    
            {
    
                int v=G[u][i].v;//u的i号后继结点编号为v
    
                inDegree[v]--;
    
                if(inpegree[v]==0)
    
                    q.push(v);
    
                //用ve[u]来更新u的所有后继结点
    
                if(ve[u]+G[u][i].w> ve[v])
    
                    ve[v]=ve[u]+G[u][i].w;
    
            }
    
        }
    
        if(toporder.size()== n)
    
            return true;
    
        else
    
            return false;
    
    }

    同理,如图10-64所示,从事件V出发通过相应的活动ar1~ark可以到达k个事件V1~Vk,活动的边权为length[r1]~length[rk]。假设已经算好了事件V1~Vk的最迟发生时间xl[j1]vl[jk],那么事件Vi的最迟发生时间就是vl[j1]-length[r1]~vl[jk]-length[rk]中的最小值。此处取最小值是因为必须保证Vj1~Vjk的最迟发生时间能被满足;可以通过下面这个公式辅助理解。

     和ve数组类似,如果需要算出vl[i]的正确值,vl[j1]~vl[jk]必须已经得到。这个要求与ve数组的刚好相反,也就是需要在访问某个结点时保证它的后继结点都已经访问完毕,而这可以通过使用逆拓扑序列来实现。幸运的是,不必再做一次逆拓扑排序来得到逆拓扑序列,而是可以通过颠倒拓扑序列来得到一组合法的逆拓扑序列。此时会发现,在上面实现拓扑排序的过程中使用了栈来存储拓扑序列,那么只需要按顺序出栈就是逆拓扑序列。而当访问逆拓扑序列中的每个事件Vi时,就可以遍历Vi的所有后继结点Vj1~Vjk,使用vI[j1]~vl[jk]来求出vl[i]。

    这部分的代码如下所示:

    fill(vl,v1+n,ve[n-1]);//v1数组初始化,初始值为终点的ve值
    
    //直接使用toporder出栈即为逆拓扑序列,求解v1数组
    
    while(!topOrder.empty())
    
    {
    
        int u=topOrder.top();//栈顶元素为u
    
        topOrder.pop();
    
        for(int i=0;i<G[u].size();i++)
    
        {
    
            int v=G[u][i].v;//u的后继结点v
    
            //用u的所有后继结点v的v1值来更新v1[u]
    
            if(vl[v]-G[u][i].w < vl[u])
    
                vl[u]=vl[v]-G[u][i].w;
    
        }
    
    }
    
    

            通过上面的步骤已经把求解关键活动的过程倒着推导了一遍,下面给出上面过程的步骤总结,即“先求点,再夹边”

    ①按拓扑序和逆拓扑序分别计算各顶点(事件)的最早发生时间和最迟发生时间:

    ②用上面的结果计算各边(活动)的最早开始时间和最迟开始时间:

    e[i-] = l[i-i]的活动即为关键活动。

    主体部分代码如下(适用汇点确定且唯一的情况,以n-1号顶点为汇点为例):【主体代码】

    求取关键路径:

    
    //遍历邻接表的所有边,计算活动的最早开始时间e和最迟开始时间1
    
    for(int u=0;u<n;u++)
    
    {
    
        for(int i=0;i<G[u].size();i++)
    
        {
    
            int v=G[u][i].v,w=G[u][i].w;
    
            //活动的最早开始时间e和最迟开始时间1
    
            int e=ve[u],l=vl[v]-w;
    
            //如果e==1,说明活动u->v是关键活动
    
            if(e==1)
    
            printf("%d->%d\n",u,v);//输出关键活动}
    
        }
    
        return ve[n-1];//返回关键路径长度
    
    }

     

     

    在上述代码中,没有将活动的最早开始时间e和最迟开始时间l存储下来,这是因为一般来说el只是用来判断当前活动是否是关键活动,没有必要单独存下来。如果确实想要将它存储下来,只需要在结构体Node中添加域e1即可。

    如果事先不知道汇点编号,有没有办法比较快地获得关键路径长度呢?当然是有办法的,那就是取ve数组的最大值。原因在于,ve数组的含义是事件的最早开始时间,因此所有事件中ve最大的一定是最后一个(或多个)事件,也就是汇点。于是只需要在fill函数之前添加一小段语句,然后改变下vl函数初始值即可,代码如下:

    int maxLength = 0;
    
    for(int i=0; i<n; ++i)
    
    {
    
        if(ve[i] > maxLength)
    
            maxLength = ve[i];
    
    }
    
    fill(vl, vl + n, maxLength);

     

    展开全文
  • 关键路径 关键路径是求「工程上时间最短的问题」的方法 阅读本文前请先了解 拓扑排序 拓扑排序主要解决「工程是否能顺序进行」的问题,关键路径在拓扑排序的基础上解决「工程最短时间的问题」。 一、工程最短时间 ...

    关键路径

    关键路径是求「工程上时间最短的问题」的方法

    阅读本文前请先了解

    拓扑排序

    拓扑排序主要解决「工程是否能顺序进行」的问题,关键路径在拓扑排序的基础上解决「工程最短时间的问题」。

    一、工程最短时间

    image-20201231135025743

    工程时间最短的问题:

    按照工厂上图生产一辆汽车,外壳、发动机、轮子和其他部件可以同时建造。

    (1)求组装完成最短需要多少时间?

    (2)如何缩短最短时间?

    答案:

    (1)

    因为所有部件可以同时建造,所以只要最长时间的「发动机」不建造完毕集中部件就无法进行。所以:「工程最短时间」就是通向汇点的和 最长的权重。(最长权重的路径也叫做「关键路径」)

    上图 开始 -> 发动机完成 -> 部件集中完成 -> 组装完成 就是最长权重,组装完成最短用时 6

    (2)

    关键路径性质:缩短关键路径上的时间就能缩短最短时间(但是缩短的同时关键路径会动态发生变化,比如发动机建造时间 <= 2 ,继续缩短发动机建造时间就没用了)

    二、AOE (Activity On Edge)网络

    找出最长权重的路径就是关键路径。所以边必须有权重。(没权重咋算??)

    我们要在「拓扑排序」AOV 网的基础上介绍 AOE 网,区别如下

    • AOV(Activity On Vertex):活动在顶点上,边没有权重
    • AOE(Activity On Edge):活动在边上,边有权重

    定义如下:

    • 边(Edge)称之为「活动」(比如造轮子)

    • 顶点(Vertex)称之为「事件」(比如说轮子完成)

    image-20201231135025743

    三、关键路基算法

    3.1 关键路径算法原理

    我们如何求出关键路径?

    我们举个例子:

    小明有 2 个小时的作业,回家一共有 4 个小时做作业的时间。他可以选择一开始就做,或者因为「ddl 综合征」最后 2 小时才开始做。此时「做作业最早的时间」和「做作业的最晚时间」是不等的。

    老师知道小明的情况后将小明的作业增加到了 4 个小时的量,小明做作业的时间还是 4 个小时。小明只能回家就开始做作业才能做完。此时「做作业最早的时间」和「做作业的最晚时间」是相等的。

    「做作业最早的时间」和「做作业的最晚时间」是相等的说明:如果做作业的时间延误,将会导致整个工期延误,做作业的时间缩短,整个工期的最短时间就会缩短。

    我们将「做作业」抽象为「活动」Activity,「作业完成」抽象为「事件」Event

    关键路径定义:活动的最早发生时间和最晚发生时间相等的路径就是关键路径

    求关键路径我们只需要求出「活动最早发生时间」和「活动最晚发生时间」即可。


    3.2 关键路径算法

    (1)参数定义

    求关键路径我们只需要求出「活动最早发生时间」和「活动最晚发生时间」即可。

    但是在 AOE 图中,「活动」就是向量边,求向量边一般是困难的,我们可以借助顶点来求边。

    参数定义如下:

    • etv(Earliest Time of Vertex):顶点最早发生时间,也就是「事件最早发生时间」
    • ltv(Lastest Time of Vertex):顶点最晚发生时间,也就是「事件最晚发生时间」
    • ete(Earliest Time of Edge):边最早发生时间,也就是「活动最早发生时间」
    • lte(Lastest Time of Edge):边最晚发生时间,也就是「活动最晚发生时间」

    我们通过 etv 求 ete,ltv 求 lte


    (2)算法步骤

    步骤如下:(结合代码理解)

    • 通过拓扑排序求出 etv「事件最早发生时间」

      e t v [ j ] = m a x { e t v ( i ) + w e i g h t < i , j > } etv[j] = max\{etv(i) + weight<i,j>\} etv[j]=max{etv(i)+weight<i,j>}

    • 通过「反向推导」求出 ltv「事件最晚发生时间」

      l t v [ i ] = m a x { e t v ( j ) − w e i g h t < i , j > } ltv[i] = max\{etv(j) - weight<i,j>\} ltv[i]=max{etv(j)weight<i,j>}

    • 通过 etv 求出 ete「活动最早发生时间」

      活动最早发生时间等于 f r o m from from(箭头开始方向的事件最早发动时间)

    • 通过 ltv 求出 lte「活动最晚发生时间」

      活动最晚发生时间等于 t o − w e i g h t to - weight toweight(箭头结束方向的事件发生时间 - 权重)

    • 通过 lte - ete 求出关键路径


    四、代码

    示例如下图:

    image-20201231150824801

    public class CriticalPath {
        /** 边 */
        static class Edge{
            /** 权重 */
            int weight;
            /** 出度指向的点 */
            int toVertex;
            Edge next;
            public Edge(int weight, int toVertex, Edge next) {
                this.weight = weight;
                this.toVertex = toVertex;
                this.next = next;
            }
        }
        /** 顶点 */
        static class Vertex{
            /** 入度 数量 */
            int inNumber;
            /** 顶点信息 */
           Integer data;
            /** 第一条边 */
            Edge firstEdge;
            public Vertex(int inNumber, Integer data, Edge firstEdge) {
                this.inNumber = inNumber;
                this.data = data;
                this.firstEdge = firstEdge;
            }
        }
        static void criticalPath(List<Vertex> graph){
            //顶点数量
            int length = graph.size();
            //边数量
            int numOfEdges = 0;
            for (Vertex vertex : graph) {
                Edge edge = vertex.firstEdge;
                while (edge!=null){
                    numOfEdges ++;
                    edge = edge.next;
                }
            }
            //事件最早发生时间
            int[] etv = new int[length];
            //事件最晚发生时间
            int[] ltv = new int[length];
            //活动最早发生时间
            int[] ete = new int[numOfEdges];
            //活动最晚发生时间
            int[] lte = new int[numOfEdges];
            //1. 通过拓扑排序求 etv 「事件最早发生时间」
            //etvStack 用于储存拓扑排序后的顺序
            Stack<Vertex> etvStack = new Stack<>();
            //stack 用于拓扑排序
            Stack<Vertex> stack = new Stack<>();
            for (Vertex vertex : graph) {
                if (vertex.inNumber == 0){
                    stack.push(vertex);
                }
            }
            while (!stack.isEmpty()){
                Vertex pop = stack.pop();
                //储存拓扑排序后的结构
                etvStack.push(pop);
                //遍历出度
                Edge edge = pop.firstEdge;
                while (edge != null){
                    Vertex vertex = graph.get(edge.toVertex);
                    vertex.inNumber --;
                    if (vertex.inNumber == 0){
                        stack.push(vertex);
                    }
                    //赋值更大的距离给 etv
                    if (etv[pop.data] + edge.weight > etv[edge.toVertex]){
                        etv[edge.toVertex] = etv[pop.data] + edge.weight;
                    }
                    edge = edge.next;
                }
            }
            //2.通过 etv 反向推导求出 ltv「事件最晚发生时间」
            System.out.println("====etv====");
            for (int i = 0; i < etv.length; i++) {
                System.out.print("V"+i +" = "+etv[i]+" ");
            }
            System.out.println();
    
            //初始化 ltv
            Integer endVertex = etvStack.peek().data;
            for (int i = 0; i < ltv.length; i++) {
                ltv[i] = etv[endVertex];
            }
            while (!etvStack.isEmpty()) {
                Vertex pop = etvStack.pop();
                Edge edge = pop.firstEdge;
                while (edge != null) {
                    //赋值更小的距离给 ltv
                    if (ltv[pop.data] > ltv[edge.toVertex] - edge.weight) {
                        ltv[pop.data] = ltv[edge.toVertex] - edge.weight;
                    }
                    edge = edge.next;
                }
            }
            System.out.println("====ltv====");
            for (int i = 0; i < ltv.length; i++) {
                System.out.print("V"+i +" = "+ltv[i]+" ");
            }
            System.out.println();
            //3. 通过 etv 求 ete
            int index = 0;
            for (Vertex vertex : graph) {
                Edge edge = vertex.firstEdge;
                while (edge != null){
                    ete[index++] = etv[vertex.data];
                    edge = edge.next;
                }
            }
            System.out.println("====ete====");
            for (int i = 0; i < ete.length; i++) {
                System.out.print("E"+i +" = "+ete[i]+" ");
            }
            System.out.println();
            //4. 通过 ltv 求 lte
            index = 0;
            for (Vertex vertex : graph) {
                Edge edge = vertex.firstEdge;
                while (edge != null){
                    lte[index++] = ltv[edge.toVertex] - edge.weight;
                    edge = edge.next;
                }
            }
            System.out.println("====lte====");
            for (int i = 0; i < lte.length; i++) {
                System.out.print("E"+i +" = "+lte[i]+" ");
            }
            System.out.println();
            //5. 用 lte - ete 求关键路径 
            System.out.println("====关键路径====");
            for (int i = 0; i < ete.length; i++) {
                if (lte[i] - ete[i] == 0) {
                    System.out.print("E"+i+" ");
                }
            }
            return ;
        }
    
        /** 测试 */
        public static void main(String[] args) {
            char[] vertices = new char[]{'A','B','C','D','E','F','G'};
            Edge e3 = new Edge(2, 4, null);
            Edge e2 = new Edge(1, 3, e3);
            Edge e1 = new Edge(3, 2, e2);
            Edge e0 = new Edge(2, 1, e1);
            Edge e4 = new Edge(1, 5, null);
            Edge e5 = new Edge(1, 5, null);
            Edge e6 = new Edge(1, 5, null);
            Edge e7 = new Edge(1, 5, null);
            Edge e8 = new Edge(2, 6, null);
            Vertex a = new Vertex(0, 0, e0);
            Vertex b = new Vertex(1, 1, e4);
            Vertex c = new Vertex(1, 2, e5);
            Vertex d = new Vertex(1, 3, e6);
            Vertex e = new Vertex(1, 4, e7);
            Vertex f = new Vertex(4, 5, e8);
            Vertex g = new Vertex(1, 6, null);
            ArrayList<Vertex> graph = new ArrayList<>();
            graph.add(a);
            graph.add(b);
            graph.add(c);
            graph.add(d);
            graph.add(e);
            graph.add(f);
            graph.add(g);
            criticalPath(graph);
        }
    }
    

    结果:

    ====etv====
    V0 = 0 V1 = 2 V2 = 3 V3 = 1 V4 = 2 V5 = 4 V6 = 6 
    ====ltv====
    V0 = 0 V1 = 3 V2 = 3 V3 = 3 V4 = 3 V5 = 4 V6 = 6 
    ====ete====
    E0 = 0 E1 = 0 E2 = 0 E3 = 0 E4 = 2 E5 = 3 E6 = 1 E7 = 2 E8 = 4 
    ====lte====
    E0 = 1 E1 = 0 E2 = 2 E3 = 1 E4 = 3 E5 = 3 E6 = 3 E7 = 3 E8 = 4 
    ====关键路径====
    E1 E5 E8 
    
    展开全文
  • 关键路径

    千次阅读 2017-11-29 22:52:24
    还有,关键路径是可以变化的,提高某些关键活动的速度可能使原来的非关键路径变为新的关键路径,因而关键活动的速度提高是有限度的。例如,图9-15中关键活动a1由6改为4后,路径{0,2,4,6,8}也变成了关键路径,此时,...

    一、AOE网的概念


            与上一文AOV网相对应的是AOE网,即边表示活动的网络。它与AOV网比较,更具有使用价值,通常用它表示一个工程的计划或进度。

           AOE网是一个有向带权图,图中的边表示活动(子工程),边上的权表示活动的持续时间,即完成该活动所需要的时间;图中的顶点表示事件,每个事件是活动之间的转接点,即表示它的所有入边活动到此完成,所有出边活动从此开始。AOE网中有两个特殊的顶点(事件):一个称做源点,它表示整个工程的开始,亦即最早活动的起点,显然

    它只用出边,没有;另一个称为汇点,它表示整个工程的结束,亦即最后活动的终点,显然它只有入边,没有出边。除这两个顶点外,其余顶点都既有入边,也有出边,是入边活动和出边活动的转接点。在一个AOE网中,若包含n个时间,通常另源点为第0个事件(假定从0开始编号),汇点为第n-1个事件,其余事件的编号(即顶点序号)分别从1至n-2。

           图9-15就是一个AOE网,该网中包含11项活动和9个事件。例如,边<0,1>表示活动a1,持续时间(即权值)为6,假定以天为单位,即a1需要6天完成,它以V0事件为起点,以V1事件为终点;边<4,6>和<4,7>分别表示活动a7和a8,它们的持续时间分别为9天和7天,它们均以V4事件为起点,但分别以V6和V7时间为终点。该网中 的源点和汇点分别为第0个事件V0和最后一个时间V8,它们分别表示整个工程的开始和结束。




    二、时间的最早发生时间


            在AOE网中,一个顶点事件发生或出现必须在它的所有入边活动(或称前驱活动)都完成之后,也就是说,只要有一个入边活动都没完成,该事件就不可能发生。显然,一个时间的最早发生时间是它的所有入边活动,或者说最后一个入边活动刚完成的时间。同样,一个活动的开始必须在它的起点事件发生之后,也就是说,一个顶点事件没有发生时,它的所有出边活动(或称后继活动)都不可能开始。显然一个活动的最早开始时间是它的起点事件的最早发生时间。

            一个事件的发生有待于它的所有入边活动的全部完成,而每个入边活动的开始和完成又有待于前驱事件的发生,而每个前驱事件的发生又有待于它们的所有入边活动的完成,.......总之,一个事件发生在从源点到该顶点的所有路径上的活动都完成之后,显然,其最早发生时间应等于从源点到该顶点的所有路径上的最长路径长度。这里所说的路径长度是指带权路径长度,即等于路径上所有活动的持续时间之和。例如,从源点V0到顶点V4共有两条路径,长度分别为7和5,所以V4的最早发生时间为7。从源点V0到汇点V8有多条路径,通过分析可知,其最长路径长度为18,所以汇点V8的最早发生时间为18。汇点事件发生表明整个工程的所有活动都已完成,所以完成图9-15所对应的工程至少需要18天。

            现在接着讨论如何从源点V0的最早发生时间0出发,求出其余各事件的最早发生时间,求一个时间Vk的最早发生时间(即从源点V0到Vk的最长路径长度)的常用方法是:由它的每个前驱事件Vj的最早发生时间(即从源点V0到Vj的最长路径长度)分别加上相应入边<j,k>上的权,其值最大者就是Vk的最早发生时间。由此可知,必须按照拓扑序列中的顶点次序(即拓扑有序)求出各个事件的最早发生时间,这样才能保证在求一个事件的最早发生时间,它的所有前驱事件的最早发生时间都已求出。

           设ve[k]表示Vk事件的最早发生时间,ve[j]表示Vk的一个前驱事件Vj的最早发生时间,dut(<j,k>)表示边<j,k>上的权,p表示Vk顶点所有入边的集合,则AOE网中每个事件Vk(0<=k<n-1)的最早发生时间可由下式,按照拓扑有序计算出来。ve[k]=max{ ve[j]+dut(<j,k>)}         (1<=k<=n-1,<j,k>属于p,ve[0]=0)


    三、事件的最迟发生时间


             在不影响整个工程按时完成的前提下,一些事情可以不在最早发生时间发生,而允许向后推迟一些时间发生,把最晚必须发生的时间叫做该事件的最迟发生时间。同样,在不影响整个工程按时完成的前提下,一些活动可以不在最早开始时间开始,而允许向后推迟一些时间开始,把最晚必须开始的时间叫做该活动的最迟开始时间。 AOE网中任一个事件若在最迟发生时间仍没有发生或任一项活动在最迟开始时间仍没有开始,则必将影响整个工程的按时完成,使工期拖延。若用Vl[k]表示顶点Vk事件的最迟发生时间,用l[i]表示Vk的一条入边<j,k>上活动ai最迟开始时间,用dut(<j,k>)表示ai的持续时间,则有:l[i]=vl[k]-dut(<j,k>)

            因ai活动的最迟完成时间也就是它的终点事件Vk的最迟发生时间,所以ai的最迟开始时间应等于Vk的最迟发生时间减去ai的持续时间,或者说,要比Vk的最迟发生时间提前ai所需的时间开始。

            为了保证整个工程的按时完成,所以把汇点的最迟发生时间定义为它的最早发生时间,即vl[n-1]=ve[n-1]。其他每个事件的最迟发生时间应等于汇点的最迟发生时间减去从该事件的顶点到汇点的最长路径长度,或者说,每个事件的最迟发生时间比汇点的最迟发生时间所提前的时间应等于从该事件的顶点到汇点的最长路径上所有活动的持续时间之和。求一个事件Vj的最迟发生时间常用方法是:由它的每个后继时间Vk的最迟发生时间分别减去相应出边<j,k>上的权,其值最小者就是Vj的最迟发生时间。由此可知,必须按照它的所有后继事件的最迟发生时间都已求出。设vl[j]表示待求的Vj事件的最迟发生时间,vl[k]表示Vj的一个后继时间Vk的最迟发生时间,dut(<j,k>)表示边<j,k>上的权,s表示Vj顶点的所有出边的集合,则AOE网中每个事件Vj(0<=j<=n-1)的最迟发生时间与下式,按照逆拓扑有序计算出来:

                  ve[n-1]     (j=n-1)

          vl[j]=

                   min{ vl[k]-dut<j,k>}                 (0<=j<=2,<j,k>属于s)


    四、活动的最早和最迟开始时间


            AOE网中每个事件的最早发生时间和最迟发生时间计算出来后,可根据他们计算出每个活动的最早开始时间和最迟开始时间。设事件vj的最早发生时间为ve[j],它的一个后继事件vk的最迟发生时间为vl[k],则边<j,k>上的活动ai的最早开始时间e[i]和最迟开始时间l[i]的计算公式重新列出如下:

                  e[i]=ve[j]

                  l[i]=vl[k]-dut(<j,k>) 

            根据此计算公式可计算出AOE网中每一个活动ai的最早开始时间e[i]、最迟开始时间l[i]和开始时间余量l[i]-e[i]。


    五、关键路径和关键活动


             在图9-16中,有些活动的开始时间余量不为0,表明这些活动不在最早开始时间开始,至多向后拖延相应的开始时间余量所规定的时间开始也不会延误整个工程的进展。例如对于活动a5,它最早可以从整个工程开工后的第4天开始,至多向后拖延两天,即从第6天开始。有些活动的开始时间余量为0,表明这些活动只能在最早时间开始,并且必须在持续时间内完成,否则将拖延整个工期。把开始时间余量为0的活动称为关键活动,由关键活动所形成的从源点到汇点的每一条路径称为关键路径。图9-15中的关键路径只有一条,即为{0,1,4,6,8},如图9-17所示。


            关键路径实际上机就是从源点到汇点具有最长路径长度的那些路径,即最长路径。这很容易理解,因为整个工程的工期就是按照最长路径长度计算出来的,即等于该路径上所有活动的持续时间之和。当然一条路径上的活动只能串行进行,若最长路径上的任一活动不在最早开始时间开始,或不在规定的持续时间内完成,都必然会延误整个工期,所以每一项活动的开始时间余量为0,故它们都是关键活动。

           求出一个AOE网的关键路径后,可通过加快关键活动(即缩短它的持续时间)来实现缩短整个工程的工期。但当同时存在多条关键路径时,并不是加快任何一个关键活动都可以缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到这个目的。还有,关键路径是可以变化的,提高某些关键活动的速度可能使原来的非关键路径变为新的关键路径,因而关键活动的速度提高是有限度的。例如,图9-15中关键活动a1由6改为4后,路径{0,2,4,6,8}也变成了关键路径,此时,再提高a1的速度也不能使整个工程的工期提前。


    6、求AOE网中关键路径的算法描述

        

            假定一个AOE网用邻接表类的对象gr表示,下面是求其关键路径的算法描述。

    	//求AOE网中关键路径的算法描述
    	public static void criticalPath(LinkedGraph gr,int[][] cc)
    	{
    		//求用邻接表类对象gr表示的AOE网中的关键路径,相关数据存于数组cc中
    		//定义相关的变量,其中,用n表示顶点数,数组b表示邻接表的表头向量
    		int i,j,k,m=0,n=gr.vertices();
    		EdgeNode p,b[]=gr.getArray();
    		//定义具有n个元素的3个一维整型数组v,ve和vl
    		int [] v=new int [n];              //用v保存拓扑排序的顶点序列
    		int [] ve=new int[n];              //用ve保存每个事件的最早发生时间
    		int [] vl=new int[n];              //用vl保存每个事件的最迟发生时间
    		//调用拓扑排序算法,使排序结果存于数组v中
    		if(TopoSort(gr,v)==false)
    		{
    			return;
    		}
    		//给每个事件的最早发生时间置初值0
    		for(i=0;i<n;i++)
    		{
    			ve[i]=0;
    		}
    		for(i=0;i<n;i++)
    		{
    			j=v[i];
    			p=b[j];
    			while(p!=null)
    			{
    				k=p.adjvex;
    				if(ve[k]<ve[j]+p.weight)
    				{
    					ve[k]=ve[j]+p.weight;
    					p=p.next;
    				}
    			}
    		}
    		//把每个事件的最迟发生时间都置为ve[n-1]的值,以作为它们的初值
    		for(i=0;i<n;i++)
    		{
    			vl[i]=ve[n-1];
    		}
    		//求出每个事件的最迟发生时间
    		for(i=n-1;i>=0;i--)
    		{
    			j=v[i];
    			p=b[j];
    			while(p!=null)
    			{
    				k=p.adjvex;
    				if(vl[j]>vl[k]-p.weight)
    				{
    					vl[j]=vl[k]-p.weight;
    					p=p.next;
    				}
    			}
    		}
    		//计算每项活动的最早开始时间,最迟开始时间,以及开始时间余量
    		for(i=0;i<n;i++)                        //依次扫描邻接表中的每个边结点
    		{
    			p=b[i];                             //把vi邻接点表的表头指针赋给p
    			while(p!=null)
    			{
    				j=p.adjvex;                     //Vj是vi的一个后继顶点事件
    				cc[m][0]=i;                     //保存有向边<i,j>的起止序号
    				cc[m][1]=j;              
    				cc[m][2]=p.weight;              //保存<i,j>上的权值
    				cc[m][3]=ve[i];                 //保存<i,j>上活动的最早开始时间
    				cc[m][4]=vl[j]-p.weight;        //保存<i,j>上活动的开始时间余量
    				cc[m][5]=vl[j]-p.weight-ve[i];  //保存<i,j>上活动的开始时间余量
    				m++;                            //下标m值增1
    				p=p.next;                       //使p指向vi顶点的下一个边结点
    				
    			}
    		}
    	}


                






    展开全文
  • 关键路径法典型范例

    千次阅读 2020-12-21 09:49:53
    在项目管理中,关键路径网络终端元素的元素序列,该序列具有最长的总工期并决定了整个项目的最短完成时间。绘制其项目网络图如图3-2所示。 一个项目可以有多个并行的关键路径。另一个总工期比关键路径的总工期...
  • 拓扑排序以及求解关键路径

    千次阅读 2019-10-29 17:14:33
    拓扑排序以及求解关键路径都是属于有向无环网的应用 拓扑排序:解决工程能否顺序进行的问题 介绍2个概念 AOV网:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示...
  • 图——关键路径

    万次阅读 多人点赞 2019-04-02 09:10:27
    活动的最早开始时间和最晚开始时间相等,则说明该活动时属于关键路径上的活动,即关键活动。 经过比较,得出关键活动有:a0, a2, a3, a4,画出示意图如下: 该AOE网有两条关键路径。 所以,通过此案例也...
  • 关键路径计算

    万次阅读 多人点赞 2017-09-03 13:58:48
    计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。  先来看看四个特征属性的含义:  Ø  Ve(j):是从始点开始到顶点Vk的最大路径长度 ...
  • AOE网络-关键路径

    万次阅读 多人点赞 2018-10-15 18:25:32
    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。...在关键路径这个问题中,AOE网络的是“Activity On Edge”,即图上的每一条边表示的是一个活动,顶点作为各个“入度...
  • 图之关键路径

    万次阅读 2016-11-23 21:00:40
    图之关键路径
  • 关键路径详细原理

    千次阅读 2018-07-18 20:30:21
     关键路径,顾名思义,就是一个程序中最关键的路径,它关系到整个程序的时间进度,而关键二字临界点。 我们需要引进两个概念,AOE和AOV网。 二、AOE和AOV网  AOE和AOV网都是一个大型程序的示意图。而AOV关注...
  • 简单理解关键路径

    千次阅读 多人点赞 2020-03-03 20:40:09
    一,关键路径问题的相关概念 通常,一个项目可以被拆分成多个子项目,多个子项目间会具有并行和串行的特点。...关键路径问题也即从多个子项目中流程中找到影响项目整体运营时间的关键路径。 对以上问题进行建...
  • 数据结构之——关键路径

    千次阅读 2020-06-06 23:07:57
    边活动(Activity On Edge, AOE)网是用带权的边集表示活动,用顶点表示事件的有向图,而用边权表示活动完成需要的时间。 如下图所示,边a1 -a6表示需要学习的课程,也就是“活动”,边权表示课程学习需要的时间;...
  • 关键路径(AOE网)

    千次阅读 2020-02-25 18:27:53
    AOE网中的最长路径被称为关键路径(即该工程的最短完成时间) 有读者可能会疑惑,举个例子,程序员要先学完《概率数学》(假设2学时)和《C语言程序设计》(5学时)才能学《数据结构》,所以要想学《数据结构》就...
  • 经典算法之关键路径

    千次阅读 多人点赞 2018-07-19 16:29:56
    问题提出: 设一个工程有11项活动,9个事件,事件V1 ----- 表示整个工程开始,事件V9 ----- 表示整个工程结束。 每个事件的开始必须是它之前的活动已完成。...关键路径:AOE-网中,从起点到终点最长...
  • 由上述结果可知,关键路径e()=l()的是活动2、5、7,则关键路径为{事件1,事件3,事件4,事件6} 4、关键路径的意义和注意事项 1)关键路径上的所有活动都是关键活动,它是决定整个工程的关键因素,因此可通过加快...
  • 关键路径C++实现

    千次阅读 2017-04-24 15:14:53
    :在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径。 关键活动 :关键路径上的活动称为关键活动。 关键活动:e[i]=l[i]的活动  由于AOE网中的某些...
  • 关键路径算法

    千次阅读 2016-04-06 18:09:12
    关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。 1. 什么是拓扑排序? 举个例子先:一个软件专业的学生学习一系列的课程,其中一些课程必须再学完它的基础...
  • 数据结构之图的关键路径

    千次阅读 2018-11-06 11:18:43
    title: 数据结构之图的关键路径 tags: 数据结构与算法之美 一、AOE和AOV网 1.AOE网 AOE-网:用边表示活动的网,是一个带权的有向无环图,其中,顶点表示事件弧表示活动,权表示活动持续的时间,通常一个AOE-网可...
  • 项目关键路径重要功能都已经完成,而且可以投入使用。  最长路径意思很明显,就是耗时最长的。项目后期维护,其实工作量非常大,有时会拖很久。  一般来说,最长路径包含关键路径。有时也不一定,可能会包含...
  • CPM关键路径

    千次阅读 2021-04-22 17:09:05
    目录CPM关键路径法定义构造方法CPM中节点表示例题关键路径的意义: CPM关键路径法 定义 关键路径法(CriticalPath Method, CPM)是一种基于数学计算的项目计划管理方法,是网络图计划方法的一种。关键路径法将项目...
  • 【笔记】AOE网与关键路径

    万次阅读 多人点赞 2017-12-02 01:06:32
    AOE网 关键路径关键路径的算法实现
  • AOE图和关键路径的求解

    千次阅读 2019-10-24 00:02:21
    AOE网和关键路径 本文算是相对知识密度较大的文章,建议看的时候仔细一点,并在迷惑的地方搜索其他文章。 文章目录AOE网和关键路径AOE网和AOV网一些概念关键路径关键路径相关量工程规划工程规划 AOE网和AOV网 ...
  • 项目关键路径

    千次阅读 2016-06-23 17:53:42
    项目关键路径,在项目管理中,关键路径网络终端元素的元素的序列,该序列具有最长的总工期并决定了整个项目的最短完成时间。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目...
  • Project的关键路径、关键任务

    千次阅读 2019-12-07 14:07:44
    Project中网络图的关键路径 project功能很强大 上面这些均会自动生成,若过你的project突然不能显示关键任务关键路径了,不要慌,将你设置的完成百分比设回到0,然后你就会发现关键路径神奇的出来了 ...
  • 数据结构算法之关键路径

    千次阅读 2020-07-14 18:41:23
    关键路径 文章目录: 基本概念 关键路径的构造过程 关键路径的特点 1.基本概念 首先要了解AOE网和关键路径的基本概念 这里详细说明一下,AOE网和AOV网的区别和联系: 联系:都代表的是有向无环图。 区别: 1.AOE...
  • 最短路经-关键路径的实现 最短路径 最短路径是:如果从某顶点出发,这个顶点称为源点,经图的边到达另一顶点,这个顶点称为终点,所经过的路径不止一条,找出一条路径使的沿此路径上各边的权值之和为最小
  • 1.关键路径(Critical Path)从起点到终点的花费时间最长的一条为关键路径。 注意:在关键路径上的任务的松弛时间为0 ●最早开始时间:在关键路径上,从开始到该任务的最早执行的时间 ●最晚开始时间:关键...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 154,626
精华内容 61,850
关键字:

关键路径指的是