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