如何找到没有权重的 DAG 中的最长路径？
我知道如果 DAG 是拓扑排序的，则可以在线性时间内找到从 A 到 B 的最长路径，但我需要找到所有图中的最长路径。有没有比搜索所有顶点对之间的最长路径（这将是 O(n^3)）更快的方法？
这与寻找关键路径相同。
有一个简单的 O(n) DP 解决方案：
- 对顶点进行拓扑排序。
- 对于每个顶点
i我们将记录earliest(i)，最早可能的开始时间（所有顶点最初为 0）。处理每个顶点i按拓扑排序顺序，更新（增加）earliest(j)对于任何后继顶点j of i每当earliest(i) + length(i, j) > earliest(j).
完成此操作后，最大值earliest(i)所有顶点上的长度将是关键路径（最长路径）的长度。您可以通过从该顶点向后追踪来构造一条（通常可能有多个）最长路径，查看其前辈，看看它们中的哪一个可以将其产生为后继（即它们中的哪一个具有earliest(i) + length(i, j) == earliest(j)），迭代直到到达没有前趋的顶点。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
