直接非循环图中的最长路径

Question

如何在DAG中找到没有重量的最长路径？

我知道，如果对DAG进行拓扑排序，则可以在线性时间内找到从A到B的最长路径，但是我需要在所有图中找到最长的路径。有什么方法比搜索所有顶点对之间的最长路径（这将是O（n ^ 3））更快吗？

Answer 1

这与找到关键路径相同。

有一个简单的O（n）DP解决方案：

• 对顶点进行拓扑排序。
• 对于每个顶点，i我们将记录earliest(i)，最早的可能开始时间（所有顶点最初为0）。处理每个顶点i在拓扑-排序的顺序，更新（增加）earliest(j)对于任何后续顶点j的i每当earliest(i) + length(i, j) > earliest(j)。

完成此操作后，earliest(i)所有顶点的最大值将为关键路径的长度（最长路径）。您可以通过从该顶点向后追溯来构造一条（通常可能不止一个）最长的路径，查看其前任以查看其中哪些可以将其作为后继产生（即，哪些拥有earliest(i) + length(i, j) == earliest(j)），然后进行迭代直到碰到没有前任的顶点。