algorithm - 有向无环图中的最长路径

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) )，迭代直到你碰到一个没有前辈的顶点。