python - 有没有一种方法可以使用 Floyd-Warshall 算法给出最短路径，其中存在负权重循环而不允许重叠边缘？

Question

我们知道，如果图中出现负权重循环，Floyd-Warshall 算法的结果是无效的，那是因为在负权重循环上走多次，使得权重总和任意小。但是，如果我们指定不允许重复的边缘通过，那么权重总和在意义上是正确的。我想知道在这种情况下产生最小重量和的方法。已经尝试了算法的一些修改（包括当从某个顶点到自身的权重和为负时跳过循环）但是前任矩阵仍然很奇怪并且权重和矩阵完全没用（偶然我知道指数增加它的价值将不可避免地出现，请参阅链接）。

标签： pythonc++algorithmgraph

Answer 1

该问题的有效解决方案将意味着 P = NP，因此几乎可以肯定没有这样的解决方案。

使用多项式时间解决您的问题，您可以通过将所有边权重设置为 -1 并询问两个节点之间的最短路径来解决最长路径问题。

正如 Marzio De Biasi 在链接帖子中所证明的那样，最长轨迹问题的解决方案可用于解决最大度数为 3 的网格图上的哈密顿循环问题，方法是将两个新节点连接到左上角节点并要求最长的小径。

当限制在最大 3 度的网格图时，哈密顿循环问题仍然是 NP 完全的，正如 Christos H Papadimitriou、Umesh V Vazirani 在与旅行商问题相关的两个几何问题上所证明的那样，算法杂志，第 5 卷，第 2 期，1984 年 6 月，第 231-246 页，ISSN 0196-6774。

因此，您的问题是 NP 难的。