algorithm - 考虑到源顶点和目标顶点都可以从负循环到达，是否存在多项式时间最短路径算法？

Question

我不是要求一种算法来检查图中是否存在负循环（Bellman Ford 或 Floyd Warshall 可以做到这一点），而是是否存在一个多项式时间算法来找到两点之间的最短路径图包含至少一个从源顶点可到达的负循环，并且可以从负循环到达目标顶点。

Answer 1

如果您正在寻找一条路径（没有重复的顶点），那么这个问题是 NP 难题。您可以通过简单地将权重乘以 -1 来减少最长路径问题。

经典（只有边缘上的正权重）最短路径（在 P 中）和最长路径问题（NP 完全）之间的主要区别如下：所有多项式最短路径算法基本上都在计算最短步行，但是因为你有正边上的权重，最短的步行也是最短的路径（重复边不会减少步行的长度）。在最长路径问题中，您必须以某种方式检查路径上顶点的唯一性。

当您有负循环时，Bellman-Ford 算法会计算最多有 N 条边的最短步行的长度。