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