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