为什么在图中找到最长路径是NP困难的

Question

这个链接提到：

加权图中两个给定顶点 s 和 t 之间的最长路径 G 与图 −G 中的最短路径相同，由 G 导出 将每个权重更改为其负数。因此，如果最短路径 可以在−G中找到，那么最长路径也可以在G中找到。

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

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

• -G

  有负环，此时无法找到

  -G

  中的最短路径

• -G

  不存在负环，这种情况下Floy-Warshall或Bellman-Ford算法可以在多项式时间内找到

  -G

  中的最短路径

问题：

1. 如果不存在负环，求最长路径问题不是NP-hard，这样说对吗？

2. 在存在负环的情况下，节点之间仍然存在最长的

   simple path

   ，这是NP难找到的吗？

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

4. 如果是这样，由于

   -G

   变换，在图中找到最短的简单路径也是NP困难的，这也是正确的吗？

编辑

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

Answer 1

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

Bellman-Ford 和类似的算法，另一方面，计算图中的最短路径（注意：没有 simple），即顶点可以重复。

所以你的四个问题：

1. 不。如果

   -G

   中存在负循环，则

   G

   中根本不存在最长路径，因为你可以一直绕着循环走下去。最长的

   simple

   路径可能仍然存在，但无论有或没有负循环，问题都可以简化为哈密顿路径，因此仍然是 NP 难问题。
2. 确实如此！ （如果图是无向的。）
3. 是的
4. 是的

Answer 2

• 首先，最长路径问题一般来说是 NP-Hard（实际上是 NP-Complete）的 当没有负边沿时。我试图证明这一点 基础知识，这里；另外，为了证明 NP 完全，你可能想 检查这个一个。
• 其次，对于各种类别的图，科学家们提出了 用多项式时间解决这个问题。 DAG和树就是这样的两个 种类。
• 第三，对于DAG，一种选择是找到最短距离 在变换后的图中，-G（Sedgewick 书中提到了这一点， 第 4 版），还有另一个替代方案，请参阅此处。 两个都 以 theta(E+V) 时间运行。
• 最后，为了回答你的问题 1 到 3，我将坚持 贝瑟的回答。但对于您的问题 4，请注意，我们不做 像 -G 这样的变换，对于任意图 G。如果我们这样做，那么 它是一个 DAG。事实上，我们经常通过参考来证明最长路径问题作为NPC 哈密顿路径 - 与权重无关，更不用说负数了 重量。