NP硬最长路无环修正
我一整天都被这个问题缠住了。
在寻找图中最长的路径时，首先进行拓扑排序，然后检查相邻顶点的路径，并不断升级，选择边权最大值或其他顶点的替代路径。
因此，我们能够解决这个问题，因为拓扑排序只能对无圈图进行。因此，这类问题只能在无圈图中求解。
因此，我们能够解决这个问题，因为拓扑排序只能对无圈图进行。因此，这类问题只能在无圈图中求解。
现在，如果我提出另一个案子。如果所有的边都有相同的权重，我们不看图的循环。这个能解决吗。每当我想到这一点时，我就看不到拓扑排序的任何用途，如果我们可以选择任何源，考虑到我们必须选择最大的节点数（最长的路径）。
这也是NP难还是我们能解决这个？
PS：我在一个有向非加权图中经历了这个最长的无环路径，但是有一个算法可以解决这个最长的路径问题。
共有1个答案
不清楚你说的“不在循环中寻找”是什么意思，所以我假设你的意思是，我们不考虑在循环中的最长路径中取顶点之间的边。在这种情况下，您可以将循环压缩成单个顶点，并使用上面描述的算法。
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
我想在有向（无环）图中找到最长的路径。假设我知道起始节点-汇。路径应该从这一点开始。我在想我可以将边的权重设置为-1。有很多方法可以找到所有最短的路径，但你必须通过终点。有没有可能得到最短的路径（无论最终节点如何）？ 假设我想为节点 nr 1（汇）找到最长路径。所以这个算法给了我1-2-3-4-5-6。
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
我能够使用这个算法在一个加权DAG中找到最长的路径（使用拓扑排序，然后放松每个边）。我现在的问题是，是否有一个算法来找到DAG的前3个最长的路径？或者，有没有实现这种算法的javascript或java库？
-
我遇到了一个问题，我必须找出给定图形中的最长路径。我有一个边列表（例如，{AB，BC}），它表明在顶点/节点（A，B，C）之间有一条边。现在我想计算出可能的最长路径（不重复顶点），这样它可以覆盖从任何顶点/节点开始的最大节点。 解决这个问题的最佳方法是什么？我必须把它作为一个计划来实施。 我在谷歌上查找最小生成树、Dijkstra的算法等等。但我想不出什么最适合解决这个问题。 任何帮助或阅读参考资
-
我需要找到图中最长的路径基于边权值。对于图像上的图，它应该是4,5,3,2,1（顺序无关紧要），最好的算法是什么？如果您知道，在您的图中，每个节点都有一个对图中任何其他节点的引用（边）。算法应该改变吗？