5

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

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

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

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

4

5 回答 5

5

我会用动态编程来解决这个问题。要找到从 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 边的节点的最大成本。
于 2008-09-20T09:09:45.803 回答
2

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

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

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

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

于 2008-09-20T09:02:10.923 回答
2

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

更新：我为糟糕的格式道歉——服务器端的降价引擎显然坏了。

于 2008-09-21T01:47:27.763 回答
1

我的第一个答案，请原谅stackoverflow文化的任何非标准事物。

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

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

于 2016-05-16T12:57:49.030 回答
0

尝试 A* 方法。

A* 搜索算法

最后，对付树叶，只要把它们都引到一个终点，设定为目标。

于 2008-09-20T09:14:33.233 回答