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

当图的节点具有权重时，计算定向无环图的关键路径的最佳方法（关于性能）是什么？如何计算定向非循环图的关键路径？

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

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

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

我不知道“关键线索路径“，但我假设你的意思是this。

只有通过遍历整棵树然后比较长度才能找到带有权重的非循环图中最长的路径，因为您永远不知道树的其余部分是如何加权的。你可以在Wikipedia找到更多关于遍历树的信息。我建议，你先进行预购遍历，因为它很容易和直接实施。

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

但是如果你不这样做，那么没有什么能够真正的将你从完整的遍历中拯救出来。顺序并不重要，只要你做一个遍历并且永远不会走相同的路径两次。

2008-09-20 09:02:10

我会用动态规划解决这个问题。为了找到从S到T中的最大成本：

2008-09-20 09:09:45

尝试A *方法。

最后，处理的叶子，只是让所有的人都导致到最后一点，设定为目标。

2008-09-20 09:14:33 TraumaPony

有一篇论文声称具有这样的算法：“具有时间限制的活动网络中的关键路径”。可悲的是，我找不到免费副本的链接。短的，我只能第二种改性http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm或http://en.wikipedia.org/wiki/A *

UPDATE的想法：我的蹩脚的格式，服务器端降价发动机道歉显然打破。

2008-09-21 01:47:27

谢谢你的答案！ – 2008-09-22 11:22:38

我的第一个答案，请原谅任何非标准的东西由文化的计算器。

我认为解决方案很简单。只是否定权重并运行DAG的经典最短路径（当然，对顶点的权重进行修改）。它应该运行得相当快。（时间复杂度为O（V + E）也许）

我认为它应该当你抵消权重，最大的一个将变得最小，第二个最大的将是第二小的，等等，就好像a > b然后-a < -b 。然后运行DAG应该就足够了，因为它会找到解决方案的最小路径的否定的一个，从而找到原来的最长路径

2016-05-16 12:57:49

回答