结果矩阵 = mat[i][j] 是以顶点 i 为源点和顶点 j 为目的地的最短路径的矩阵。
我已经编写了自己的 Johnson 算法实现，我想知道它如何处理负边缘？最后，我获得的距离矩阵与我通过运行 Floyd-Warshall 获得的距离矩阵不同。当我们重新加权图表时，这是显而易见的。这是否意味着约翰逊的算法不能帮助我们找到最短路径的成本，而只能帮助我们找到哪条路径是最短的？另外，如果在结果矩阵中顶点 A 和顶点 B 之间有一条路径，成本为 0，而顶点 A 和顶点 C 之间有一条路径，成本为 0，这是否意味着 B 和 C 离 A 的距离相等？
最佳答案
Johnson 的算法确实应该返回与您使用 Floyd-Warshall 返回的路径相同的路径 - 如果您没有看到这一点，则可能意味着您的实现中某处存在错误。
您说得对，Johnson 的算法确实会重新加权图形的边，但这样做的方式相当聪明。具体来说，在新图中，虽然新图中每条路径的成本可能与原始图中的不同，但新图中路径的相对成本是与原始图中相同。从这个意义上说，无论什么路径作为新图中的最短路径返回，都必然也是原始图中的最短路径。但是，新图中这些路径的成本 不会与您的原始图匹配，因此作为约翰逊算法中的后处理步骤，您应该调整产生的成本以反转效果改变权重。
虽然没有看到您正在运行的代码，但很难说出具体出了什么问题。如果您发布包含特定代码、您正在运行的特定测试用例、您获得的特定输出以及您认为它们不正确的原因的后续问题，您可能会更幸运。
关于algorithm - 约翰逊算法负边距矩阵，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53574264/