如何计算有向无环图的关键路径？

Question

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

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

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

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

- Panagiotis Korros

Answer 1

我会使用动态规划来解决这个问题。为了找到从S到T的最大花费：

• 对图的节点进行拓扑排序，即S = x_0, x_1, ..., x_n = T。（忽略任何可以到达S或由T到达的节点。）
• 从S到S的最大花费是S的权重。
• 假设您已经计算出了从S到所有i < k的x_i的最大花费，则从S到x_k的最大花费是x_k的花费加上任何一条边指向x_k的节点的最大花费。

- James Cook

Answer 2

我对“关键路径”一无所知，但我认为你指的是this。

在具有权重的无环图中找到最长路径只能通过遍历整个树然后比较长度来实现，因为你永远不知道其余部分的权重。你可以在Wikipedia上了解更多关于树遍历的内容。我建议你选择前序遍历，因为它易于实现且直截了当。

如果你经常查询，你可能还希望在插入时增加节点之间的边缘信息，以了解它们子树的权重。这相对便宜，而重复遍历可能非常昂贵。

但是，如果你不进行全面的遍历，就没有什么可以真正拯救你。顺序并不重要，只要你进行遍历，并且不重复走同一条路径。

- Aleksandar Dimitrov

Answer 3

有一篇论文声称有一种算法可以解决这个问题：“带时间限制的活动网络中的关键路径”。可惜我找不到免费副本的链接。除此之外，我只能赞同修改http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm或http://en.wikipedia.org/wiki/A* 的想法。

更新：对于糟糕的格式，我表示歉意——服务器端的 Markdown 引擎显然出了故障。

- Hank Gay

Answer 4

这是我的第一个回答，请见谅如果有任何不符合stackoverflow文化的非标准用语。

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

我认为这应该有效，因为当你取反权重时，最大值将变成最小值，第二大的值将变成第二小的值，以此类推，就像如果a>b，那么-a<-b。然后运行DAG就足够了，因为它将找到取反路径的最小路径的解决方案，从而找到原始路径的最长路径。

- user4952610

Answer 5

尝试使用A*算法。

A*搜索算法

最后，为了处理叶子节点，只需将它们全部指向一个最终点，作为目标即可。

- TraumaPony