共有1个答案
我想我已经找到了一个解决方案，使得仍然可以使用拓扑排序。
按照常规进行拓扑排序和关键路径方法，但在计算到给定节点的最长路径时，不要只计算一条最长路径，而是为有效路径中从1到最大边的每个路径长度寻找最长路径，为这些最高得分路径中的每个路径创建一个顶点。
这基本上意味着您要探索每个节点路径中所有可能的边计数变化，这意味着最后得分最高的路径肯定是最长的路径。
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
问题：给定一个加权有向无环图（DAG）和其中的一个源顶点s，找出从s到给定图中所有其他顶点的最长距离。 请查找参考图：链接 为什么我们需要拓扑排序？我们不能简单地从源顶点使用修改后的BFS吗？为什么我们如此关心线性排序。 如果这是重复，请将我重定向到相关答案。 谢谢
-
我知道Bellman Ford算法使用负权值，但我希望我可以修改我现有的最短路径方法。
-
如何输出有向无环图的所有可能的拓扑排序？例如，给定一个图形，其中 V 指向 W 和 X，W 指向 Y 和 Z，X 指向 Z： 如何对此图进行拓扑排序以产生所有可能的结果？我能够使用广度优先搜索来获得V，W，X，Y，Z，并使用深度优先搜索来获得V，W，Y，Z，X。但无法输出任何其他种类。
-
我需要找到图中最长的路径基于边权值。对于图像上的图，它应该是4,5,3,2,1（顺序无关紧要），最好的算法是什么？如果您知道，在您的图中，每个节点都有一个对图中任何其他节点的引用（边）。算法应该改变吗？
-
我能够使用这个算法在一个加权DAG中找到最长的路径（使用拓扑排序，然后放松每个边）。我现在的问题是，是否有一个算法来找到DAG的前3个最长的路径？或者，有没有实现这种算法的javascript或java库？