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

Why finding the longest path in a graph is NP-hard

这个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 难问题呢？

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

问题：

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

  2. 在负循环存在的情况下，节点之间还有一个最长的simple path是NP难找的吗？

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

  4. 如果是这样，因为-G变换，说在图中找到最短的简单路径也是NP-也是正确的吗难吗？

编辑

这篇link更详细地解释了关于最长路径问题的困惑： https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869

这里的困惑是，最长路径问题一般要求最长的简单路径，即没有重复顶点的最长路径。由于这个原因，它可以简化为哈密顿路径问题，该问题被称为NP-hard。

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

所以你的四个问题：

  1. 没有。如果-G中存在负循环，则G中根本不存在最长路径，因为你可以一直绕着循环一直走下去。最长的 simple 路径可能仍然存在，但无论是否有负循环，问题都可以简化为哈密顿路径，因此仍然是 NP-hard。
  2. 确实如此！ （如果图形是无向的。）
  3. 对
  4. 对
  • 首先，最长路径问题一般是NP-Hard（实际上是NP-Complete）甚至 当没有负边缘时。我试图从 基础知识，here；也为了 NP-complete 的证明，你可能想 检查这个 one.
  • 其次，对于Graphs的各种分类，科学家们纷纷提出 用多项式时间解决这个问题。 DAG，和tree就是这样的两个 种类.
  • 第三，对于DAG，一个选项是找到最短距离 在转换图中，-G（这在 Sedgewick 书中提到， 第 4 版），还有另一种选择，参见 here。两个都 运行 在 theta(E+V) 时间内。
  • 最后，对于问题 1 到 3 的回答，我会坚持 。但是对于您的问题 4，请注意我们不做 像-G 一样的变换，对于任意图 G。如果我们完全这样做，那么 它是一个 DAG。实际上，我们经常通过参考 NPC 来证明最长路径问题 哈密​​顿路径 - 与权重无关，更不用说负数了 权重。