我知道在 NP-HARD 中存在以下问题：给定一个简单的图 G=(V,E)，V 中有两个顶点 v，v'，一个整数 B，以及一个非负长度函数 len：E-> Z+ ，是否有一条从 v 到 v' 长度小于 B的简单路径？
我的问题是：在与以前相同的条件下，如果我们有兴趣在 G 中找到从顶点 v 到 v' 的最长但不一定简单的路径，那么问题仍然存在于 NP-HARD 中吗？
注意：我试图减少汉密尔顿路径，但我仍然无法证明 NP 是否存在问题，可简化为我提到的这个问题。我也查过Garey & Johnson，但我什么也没找到。
我想要一点提示来证明这个问题是否是 NP-HARD。提前致谢！
不，这不是 NP 难的；您可以使用最短路径算法（例如 Bellman-Ford）通过否定边缘长度来在多项式时间内解决它。请注意，最长的路径很可能是无限的，特别是当所有边权重均为非负时。
没有负循环的图中的最短简单路径不是 NP 难的。请参阅 Cormen 的“算法简介”。可以使用 Bellman-Ford 算法求解。如果我们没有负边权重，也可以使用 Dijkstra 算法。两者都计算从单个源到图的所有其他节点的所有最短路径。因此，正如我正确理解的那样，您的第一个问题不是 NP 难题。
在不存在正循环的情况下，最长简单路径问题是不存在负循环的最短简单路径问题的对偶。也不是NP难的。
允许负循环的最短（非简单）路径是 NP 难的，因为您需要记住到节点的所有可能路径，这可能是指数的。对于允许正循环的最长（非简单）路径问题也是如此。
我希望这能回答你的问题。
如果我遗漏了任何内容或任何陈述有误，请随时纠正我。