问有向无圈加权图中前3最长路径的求法
EN

Stack Overflow用户

提问于 2016-07-21 17:32:38

回答 1查看 1.4K关注 0票数 2

我可以使用这种算法在加权DAG中找到最长的路径(使用拓扑排序，然后放松每个边)。我现在的问题是，是否有算法来查找DAG的前3条最长路径？或者，是否有实现此算法的javascript或java库？

发布于 2016-07-22 05:30:43

您可以轻松地计算第一个最长路径，并且可以使用以下算法来查找下一个最长路径：

逐个删除主最长路径的每个边，然后再运行该算法，在修改后的图上找到最长的路径，然后把删除的边放回去，再删除另一个边。

为什么这样做？

您需要一条路径--并不完全是第一条最长的路径，所以第二条最长的路径必须在至少一条边中不同，所以如果忽略一条边并为每条边找到最长的路径，那么最终您将找到一条与主最长路径不共享至少一条边的最长路径。

第三最长路径是一条与第一和第二最长路径不共享至少一条边的最长路径。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/38510780

复制

相似问题

问有向无圈加权图中前3最长路径的求法EN