在图数据结构中，我们如何使用中间节点来计算任何其他两个节点的距离？
In graph data structure how can we use intermediate node to calculate distance of any other two nodes?
在 floyd warshell 算法中，我们将任何节点 y 保留为中间节点，并通过中间节点 y 更新从一个节点到另一个节点（对于所有节点）的距离。
dp[x][y] = min( dp[x][y] , dp[x][z] + dp[z][y])
但这里的问题是 dp[x][z] 可能稍后更新，这意味着 dp[x][z] 可能不是到达 x 到 z 的最小距离，我们如何使用 dp[x][z] 来计算 dp[x][y]?
Floyd--Warshall 的实施掩盖了其工作原理的数学结构。
如果您轮流更新 dp，证明仍然可以通过，例如，对于所有 x 和 y，执行 dp'[x][y] = min(dp[x][y], min_z(dp[x][z] + dp[z][y])) 然后复制 dp = dp'.这足以确保 dp[x][y] 至多是从 x 到 y 通过我们迄今为止迭代的各种 z 的最短路径的长度。
相反，我们不会通过进行就地更新而最终低估 dp[x][y]，因为每次我们进行更新时，都有一条路径可以达到新值（具体来说，由值表示的路径dp[x][z] 后跟 dp[z][y] 的值表示的路径）。
在 floyd warshell 算法中，我们将任何节点 y 保留为中间节点，并通过中间节点 y 更新从一个节点到另一个节点（对于所有节点）的距离。 dp[x][y] = min( dp[x][y] , dp[x][z] + dp[z][y]) 但这里的问题是 dp[x][z] 可能稍后更新，这意味着 dp[x][z] 可能不是到达 x 到 z 的最小距离，我们如何使用 dp[x][z] 来计算 dp[x][y]?
Floyd--Warshall 的实施掩盖了其工作原理的数学结构。
如果您轮流更新 dp，证明仍然可以通过，例如，对于所有 x 和 y，执行 dp'[x][y] = min(dp[x][y], min_z(dp[x][z] + dp[z][y])) 然后复制 dp = dp'.这足以确保 dp[x][y] 至多是从 x 到 y 通过我们迄今为止迭代的各种 z 的最短路径的长度。
相反，我们不会通过进行就地更新而最终低估 dp[x][y]，因为每次我们进行更新时，都有一条路径可以达到新值（具体来说，由值表示的路径dp[x][z] 后跟 dp[z][y] 的值表示的路径）。