为什么需要考虑具有负环的有向图的最短路径问题

Question

考虑可能具有负循环的有向图G=(V，a，W(上的最短路径问题。我们只考虑简单路径，即没有重复顶点的路径。通过构造一个新的图G'(V，a，W'(，使得G'和G具有相同的顶点和弧，但对于每个弧，它在G'中的权重比它在G中的权重高一个常数。

显然，如果P1和P2是两条路径，并且w(P1(<w(P2(，则w’(P1(<G'中的w'(P2(。这意味着G中的最短路径也是G’中的最短路径。通过选择足够大的常数，G'的权重都可以是正的。因此，解决G’的最短路径问题就足够了。为什么对于具有负循环的图来说，最短路径问题看起来如此重要？

此外，具有负循环的最短路径问题实际上是NP困难的。如果我是对的，我们可以把有负循环的情况减少到没有负循环的情形，这个问题不应该是多项式吗？

我想我错过了什么，但我不确定是什么。

Answer 1

显然，如果p₁和p₂是两条路径，并且w(p₁(<w(P₂(在G中，然后w'(P₁；w'(P₂(在G'中。这意味着G中的最短路径也是G’中的最短路径。

否，因为如果G中路径p的权重表示为w_p，则G’内该路径的权重为w_p+n_p×c，其中n_p是路径中的边数，

c这意味着另一条道路现在可能更有利。该路径在G中可能具有更昂贵的边，但由于它包含更少的边，因此修改的边的总和可能小于G。

以下图为例：

A               B
o-------7-------o
1              / 1
o--2--o--2--o
C     D     E

这里，A和B之间的最短路径是通过C、D和E，因为和是1+2+1=6，而A和B之间的直接路径将导致7。

例如，如果我们现在用两个边来增加每条边，我们得到：

A               B
o-------9-------o
3              / 3
o--4--o--4--o
C     D     E

因此，现在路径A-C-D-E-B的权重3+4+3=14，而直接路径A-B权重9。因此，如果我们用某个常数增加每条边，最优路径可能会不同。