NP 中最长的可能非简单路径吗？
我知道下面的问题是NP-HARD中的：给定一个简单的图G=(V,E)，V中的两个顶点v，v'，一个整数B和一个非负长度函数len：E-> Z+，是否有一条从 v 到 v' 且长度小于 B 的简单路径？
我的问题是：在与之前相同的条件下，如果我们有兴趣找到 G 中从顶点 v 到 v' 的最长不一定简单路径，问题仍然是 NP-HARD 吗？
注意：我尝试减少它的 Hamilton-path，但我仍然无法证明是否 NP 中存在一个问题，可以简化为我提到的这个问题。我也查过Garey &约翰逊，但我还没有找到任何东西。
我想要一点提示来证明这个问题是否是 NP-HARD。 提前致谢！
I know that the following problem is in NP-HARD: Given a simple graph G=(V,E), two vertices v, v' in V, an integer B, and a non-negative length function len: E-> Z+, is there a simple path from v to v' with length less than B?
My question is: Given the same conditions as before, if we are interested in finding the longest not necessarily simple path in G from vertex v to v', is the problem still in NP-HARD?
Note: I've tried to reduce hamilton-path to it, but I'm still not able to prove whether
there's a problem in NP reducible to this one I'm mentioning. I've also looked up in Garey & Johnson but I haven't found anything.
I would please like a little hint to prove if this problem is NP-HARD.
Thanks in advance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
不，这不是 NP 困难的；您可以使用最短路径算法（例如 Bellman-Ford）通过否定边长来在多项式时间内解决它。请注意，最长路径可能是无限的，特别是当所有边权重均为非负时。
No, it's not NP-hard; you can use a shortest path algorithm (such as Bellman-Ford) to solve it in polynomial time by negating your edge lengths. Note that it is likely that the longest path will be infinite, particularly when all edge weights are non-negative.
图中没有负环的最短简单路径不是 NP 困难的。请参阅 Cormen“算法简介”。可以使用贝尔曼-福特算法来解决。如果我们没有负边权重，也可以使用 Dijkstra 算法。两者都计算从单个源到图的所有其他节点的所有最短路径。所以，据我正确理解，你的第一个问题不是 NP 难问题。
假定不存在正循环，最长简单路径问题是不存在负循环的最短简单路径问题的对偶问题。也不是 NP 难的。
允许负循环的最短（非简单）路径是 NP 困难的，因为您需要记住到达节点的所有可能路径，并且这可能是指数级的。对于最长（非简单）路径问题也应该如此，其中允许正循环。
我希望这能回答你的问题。
如果我遗漏了什么或者有任何表述错误的地方，请随时纠正。
Shortest simple path in a graph without negative cycles is not NP-hard. See Cormen 'An Introduction to Algorithms'. It can be solved using Bellman-Ford's Algorithm. If we have no negative edge weights one can also use Dijkstra's Algorithm. Both calculate all shortest path from a single source to all other nodes of a graph. So your first problem, as I understand you correctly, is not NP-hard.
Longest simple path problem, given that no positive cycles exist, is the dual of the shortest simple path problem with no negative cycles. Also not NP-hard.
Shortest (not-simple) path, allowing negative cycles, is NP-hard, because you need to remember all possible paths to a node, and that can be exponential. Same should be true for a Longest (not-simple) path problem, where positive cycles are allowed.
I hope that answers your question.
If I missed anything or any statement is wrong, please feel free to correct me.