algorithm - 为什么在图中找到最长路径是 NP-hard

Question

这link提及:

A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G.

那么，如果这种转换可以将最长路径问题简化为最短路径问题，那么为什么寻找最长路径问题是 NP 难问题呢？

改造后，我们有这些案例:

• -G有一个负环，这样就找不到-G中的最短路径
• -G没有负环，此时Floy-Warshall或Bellman-Ford算法可以在多项式时间内找到-G中的最短路径<

问题:

1. 如果没有负循环，寻找最长路径的问题就不是 NP 难的，这样说对吗？

2. 在存在负环的情况下，节点之间仍然存在一条 NP 难找到的最长简单路径是否正确？

3. 如果是这样，那么说在图中找到最长的简单路径是 NP-hard 是否更准确？

4. 如果是这样，由于 -G 变换，是否也可以说在图中找到最短的简单 路径也是 NP 难的？

编辑

此链接更详细地解释了最长路径问题的困惑: https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869

Answer 1

这里的混淆是最长路径问题通常要求最长的简单路径，即没有重复顶点的最长路径。因此，它可以简化为哈密顿路径问题，该问题被称为 NP-hard。

另一方面，Bellman-Ford 和类似算法计算图中的最短路径(注意:没有简单)，即顶点可以重复。

所以你的四个问题:

1. 没有。如果-G中存在负循环，则G中根本不存在最长路径，因为您可以一直绕着循环一直走下去。最长的简单路径可能仍然存在，但无论是否有负循环，问题都可以简化为哈密顿路径，因此仍然是 NP-hard。
2. 确实如此! (如果图是无向的。)
3. 是的
4. 是的