如何计算方向非循环图的关键路径？

Question

当图的节点具有权重时,计算方向非循环图的关键路径的最佳(关于性能)方法是什么？

例如,如果我有以下结构:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

关键路径应为A-> B-> F(总重量:10)

Answer 1

我会用动态编程解决这个问题.要查找从S到T的最大成本:

• 在拓扑上将图的节点排序为S = x_0,x_1,...,x_n = T.(忽略任何可以到达S或从T到达的节点)
• 从S到S的最大成本是S的重量.
• 假设您计算了所有i <k的从S到x_i的最大成本,从S到x_k的最大成本是x_k的成本加上边缘为x_k的任何节点的最大成本.

Answer 2

我对“关键路径”一无所知，但我认为你的意思是这个。

只有遍历整个树然后比较长度才能找到具有权重的非循环图中的最长路径，因为您永远不知道树的其余部分是如何加权的。您可以在维基百科上找到有关树遍历的更多信息。我建议您采用预序遍历，因为它实施起来既简单又直接。

如果您要经常查询，您可能还希望使用有关插入时子树权重的信息来增强节点之间的边。这是相对便宜的，而重复遍历可能会非常昂贵。

但如果你不这样做，就没有什么可以真正让你免于完全遍历。顺序并不重要，只要你进行遍历并且不走同一条路径两次即可。