如何计算的关键路径中的一个向环图?

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

我对<！>“关键路径<！>”没有任何线索，但我认为你的意思是此。

只能通过遍历整个树然后比较长度来查找带有权重的非循环图中的最长路径，因为您从未真正知道树的其余部分是如何加权的。您可以在维基百科中找到有关树遍历的更多信息。我建议你进行预订遍历，因为它很容易直接实现。

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

但是，如果你不这样做，没有什么可以真正拯救你完全遍历。只要您执行遍历并且永远不会两次执行相同的路径，该顺序并不重要。

Answer 2

我会解决这个动态程序。找到的最大成本从S T:

• 拓扑种节点的曲线图作为S=x_0,x_1,...,x_n=T.(忽略任何节点可以达到或将达到从T)
• 最大的成本从S S重S.
• 假设你已经计算的最高费用从S x_i我 < k，最大的成本从S x_k的费用是x_k加的最高费用的任何节点与边缘x_k.

Answer 3

有一篇论文声称有一个算法：<！>“活动网络中的关键路径，时间约束<！>”;可悲的是，我找不到免费副本的链接。除此之外，我只能提出修改 http://en.wikipedia.org/的想法。 wiki / Dijkstra％27s_algorithm 或 http://en.wikipedia.org/wiki/A *

更新：我为糟糕的格式化道歉<！>＃8212;服务器端降价引擎显然已损坏。

Answer 4

我的第一个答案，请原谅堆栈溢出文化中的任何非标准事物。

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

我认为它应该起作用，当你将否定权重时，最大的一个将变得最小，第二个最小的将是第二小的，依此类推，就好像a > b然后-a < -b。然后运行DAG应该足够了，因为它将找到被否定的最小路径的解决方案，从而找到原始路径的最长路径

Answer 5

尝试A *方法。

A *搜索算法

最后，为了对付树叶，只需将它们全部引导到最后一点，然后设定为目标。