求有向无环加权图的前3条最长路
我能够使用这个算法在一个加权DAG中找到最长的路径（使用拓扑排序，然后放松每个边）。我现在的问题是，是否有一个算法来找到DAG的前3个最长的路径？或者，有没有实现这种算法的javascript或java库？
共有1个答案
您可以很容易地计算第一条最长的路径，您可以使用以下算法来寻找下一条最长的路径：
逐条删除主最长路径的每条边，并再次运行该算法，在修改后的图上找到最长路径，然后将删除的边放回，删除另一条边。
为什么这管用？
你需要的路径不是第一条最长的路径，所以第二条最长的路径必须至少在一条边不同，所以如果你忽略一条边并为每个边找到最长的路径，你最终会找到一条最长的路径，该路径至少与主最长的路径不共享一条边。
第三条最长路径是一条最长的路径，并且与第一条和第二条最长路径至少不共享一条边。
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
我知道Bellman Ford算法使用负权值，但我希望我可以修改我现有的最短路径方法。
-
我需要找到图中最长的路径基于边权值。对于图像上的图，它应该是4,5,3,2,1（顺序无关紧要），最好的算法是什么？如果您知道，在您的图中，每个节点都有一个对图中任何其他节点的引用（边）。算法应该改变吗？
-
我遇到了一个问题，我必须找出给定图形中的最长路径。我有一个边列表（例如，{AB，BC}），它表明在顶点/节点（A，B，C）之间有一条边。现在我想计算出可能的最长路径（不重复顶点），这样它可以覆盖从任何顶点/节点开始的最大节点。 解决这个问题的最佳方法是什么？我必须把它作为一个计划来实施。 我在谷歌上查找最小生成树、Dijkstra的算法等等。但我想不出什么最适合解决这个问题。 任何帮助或阅读参考资
-
你有一辆2005年本田雅阁，油箱里还剩50英里（最大重量）。在50英里半径范围内，你可以访问哪些麦当劳的位置（图节点）？这是我的问题。 如果你有一个加权有向无环图，你如何找到在给定的权限制内可以访问的所有节点？ 我知道Dijkstra的算法，但我似乎找不到任何关于它在最小路径问题之外的用途的文档。在我的例子中，我们没有特别想结束的节点，我们只想在不超过最大权重的情况下尽可能多地结束。似乎您应该能够
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k