美文网首页
数据结构-图-关键路径

数据结构-图-关键路径

作者: arkulo | 来源:发表于2016-06-22 18:10 被阅读1558次

    github地址:https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E5%9B%BE_%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84.md

    数据结构关键路径

    AOV网络:有向图,用顶点表示活动,用弧表示活动的先后顺序
    AOE网络:有向图,用顶点表示事件,用弧表示活动,用权值表示活动消耗时间

    名词解释

    活动:业务逻辑中的行为,用边表示
    事件:活动的结果或者触发条件
    关键路径:具有最大路径长度(权重)的路径,可能不止一条


    活动的两个属性e(i)最早开始时间,l(i)最晚开始时间
    事件的两个属性ve(j)最早开始时间,vl(j)最晚开始时间

    在下面的计算过程中,就可以理解这些属性的概念了


    计算关键路径的过程

    原理:

    1. 先求出每个顶点的ve和vl值
    2. 通过这两个值就可以求出每条边的e和l值。
    3. 取e(i)=l(i)的边就是关键路径上的边,关键路径不止一条

    一、求ve(j)的值

    1. 从前向后,直接前驱节点的ve值+当前节点的边的权值(有可能多条,取最大值)
    2. 第一个顶点的ve等于0

    下表为各顶点(事件)的ve值:

    顶点 v1 v2 v3 v4 v5 v6 v7
    ve(j) 0 3 2 6 7 5 10

    二、求vl(j)的值

    1. 从后向前,直接后继节点的vl值-当前节点的边的权值(有可能多条,取最小值)
    2. 终结点的vl等于它的ve
    顶点 v1 v2 v3 v4 v5 v6 v7
    vl(j) 0 3 3 6 7 6 10

    三、求e(i)的值

    e(i):活动ai是由弧<vk,vj>表示,则活动的最早开始时间应该和事件vk的最早发生时间相等,因此,就有e(i)=ve(k)。即:边(活动)的最早开始时间等于它发出的顶点(事件)的的最早发生时间

    a1(3) a2(6) a3(2) a4(4) a5(2) a6(1) a7(3) a8(1) a9(3) a10(4)
    e(i) 0 0 0 3 3 2 2 6 7 5

    四、求l(i)的值

    l(i):活动ai是由弧<vk,vj>表示,则ai的最晚发生时间要保证vj的最迟发生时间不拖后(vj最迟发生时间为9的话,ai的最迟时间就必须是 9-活动耗时 )。因此,l(i)=vl(i)-len<vk,vj>,即:活动到达顶点的最晚发生时间减去边的权重

    a1(3) a2(6) a3(2) a4(4) a5(2) a6(1) a7(3) a8(1) a9(3) a10(4)
    l(i) 0 0 1 3 4 5 3 6 7 6

    五、求出关键边和关键路径

    e(i)==l(i)的边

    a1 a2 a4 a8 a9

    关键路径

    a1->a4->a9 和 a2->a8->a9

    相关文章

      网友评论

          本文标题:数据结构-图-关键路径

          本文链接:https://www.haomeiwen.com/subject/qbrndttx.html