7-11 关键活动(二)

    xiaoxiao2021-03-25  245

    7-11 关键活动

    鉴于我开始的做法不太好,dfs遍历了起点和终点间的全部路径,虽然是可以找到关键路径的,但是还要去重之后才能得到结果。

    于是尝试经典的关键路径算法: 

    1、通过拓扑排序计算出每个节点的最早开始时间,以及一个拓扑序列S

    2、反向遍历拓扑序列S计算出最晚开始时间

    3、节点的最早开始时间 == 最晚开始时间, 说明这节点就是瓶颈了,也就是关键节点

     

    计算最晚开始时间有一种替代方法,不需要保存步骤一中的拓扑序列S。

    构造原图的反向邻接表, 将每条边反向。

    从终点出发,根据反向的邻接表,拓扑排序一次。

     

    获得了关键节点和拓扑序列S之后,如何计算全部关键路径?

    可以dfs,但是从X节点, 在关键节点中找下一个 Y节点的时候, 需要判断 earliest[X] + length[X, Y]  == earliest[Y]

     

    如下面的有向图, 关键节点是   1 2 3 4 5, 但是关键路径是1 3 4 2 5

    节点A        节点B       边长

     

    12225500132343427451
    转载请注明原文地址: https://ju.6miu.com/read-258.html

    最新回复(0)