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

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

我会用动态规划来解决这个问题。要找到从 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 边的任何节点的最大成本。