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

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

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

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

解决方案

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

只有遍历整棵树然后比较长度，才有可能在具有权重的非循环图中找到最长的路径，因为我们永远不会真正知道树的其余部分是如何加权的。我们可以在Wikipedia上找到有关树遍历的更多信息。我建议我们进行预遍历，因为它很容易实现。

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

但是，如果我们不这样做，没有什么能真正使我们摆脱完整遍历的。顺序并不重要，只要我们进行遍历并且绝不会两次走相同的路径即可。

我将通过动态编程解决此问题。要查找从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的任何节点的最大成本。

尝试使用A *方法。

A *搜索算法

最后，要处理叶子，只需将所有叶子引向最终点，并将其设置为目标即可。

有一篇论文声称对此有一种算法："具有时间限制的活动网络中的关键路径"。可悲的是，我找不到指向免费副本的链接。除此之外，我只能提出修改http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm或者http://en.wikipedia.org/wiki/A*的想法

更新：对于服务器端Markdown引擎损坏的格式，我深表歉意。