什么是最好的（关于性能）的方式来计算定向无环图的关键路径时，图的节点有分量？

What is the best (regarding performance) way to compute the critical path of a directional acyclic graph when the nodes of the graph have weight?

例如，如果我有以下结构：

For example, if I have the following structure:

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

关键路径应该是A-> B-> F（总重量：10）

The critical path should be A->B->F (total weight: 10)

推荐答案

我不知道关于关键路径，但我相信你的意思的这个。

I have no clue about "critical paths", but I assume you mean this.

寻找最长路径中一个非循环图与重量是唯一可能通过遍历整个树，然后比较的长度，因为你从未真正知道如何树的其余部分被加权。你可以找到更多关于树的遍历在维基百科。我建议，你去pre序遍历，因为它很容易和简单的实现。

Finding the longest path in an acyclic graph with weights is only possible by traversing the whole tree and then comparing the lengths, as you never really know how the rest of the tree is weighted. You can find more about tree traversal at Wikipedia. I suggest, you go with pre-order traversal, as it's easy and straight forward to implement.

如果你要经常查询，您也不妨增加节点之间的边缘与他们的子树在插入的权重信息。这是相对便宜，而反复穿越可能会非常昂贵。

If you're going to query often, you may also wish to augment the edges between the nodes with information about the weight of their subtrees at insertion. This is relatively cheap, while repeated traversal can be extremely expensive.

但是没有什么真正拯救你一个完整的遍历，如果你不这样做。顺序并不重要，只要你做的遍历的和永远不会相同的路径两次。

But there's nothing to really save you from a full traversal if you don't do it. The order doesn't really matter, as long as you do a traversal and never go the same path twice.