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

Question

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

显然，如果P1和P2是两条路径，且G中w(P1) < w(P2)，则G'中w'(P1) < w'(P2)。这意味着 G 中的最短路径也是 G' 中的最短路径。通过选择足够大的常数，G'的权值都可以是正的。因此足以解决G'的最短路径问题。为什么最短路径问题对于负环图来说似乎是个大问题？

此外，the shortest path problem with negative cycles is actually NP-hard。如果我是对的，我们可以将负循环的情况简化为没有负循环的情况，问题不应该是多项式的吗？

我想我漏掉了什么，但我不确定是什么。

Answer 1

Clearly, if P₁ and P₂ are two paths, and w(P₁) < w(P₂) in G, then w'(P₁) < w'(P₂) in G'. This means a shortest path in G is also a shortest path in G'.

No，因为如果 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+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+4+3=14，而直接路径 A-B 的权重为 9。因此，如果我们将每条边都增加一个特定的常数，则最优路径可能会有所不同。

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

Why is there need to consider the shortest path problem for digraphs with negative cycles?

algorithm

graph

graph-algorithm

shortest-path