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

Question

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

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

Answer 1

这与找到关键路径相同。

有一个简单的 O(n) DP 解决方案：

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

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