我读到关键路径方法使用具有正权重的最长路径方法，它用于调度一组项目事件(时间值必须为正)。
就我而言，我需要找到 DAG 中具有正权重和负权重的最长路径。我能用这个问题做什么？我需要一个例子。
最佳答案
在 DAG 中查找最长路径并不真正“关心”正权重，它是使用 Dynamic Programming (DP) 完成的遵循以下公式:
D(target) = 0
D(i) = max { D(j) + w(i,j) | for each edge (i,j) }
上面是求D(v)，它是从v开始到目标结束的最大长度路径。
以 Topological Sort 的相反顺序遍历节点，它的完成时间为O(V+E)。
请注意，上面并不真正关心边缘是负还是正，它基本上是一种强力方法，当作为 DP 实现时，通过不多次重新计算相同的事情来更有效地完成。
关于algorithm - 寻找具有正负权重的 DAG 中最长路径的示例，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30902091/