algorithm - floyd warshall 中节点之间的距离

Question

This维基百科页面解释了 Floyd Warshall 算法，用于查找图中节点之间的最短路径。维基百科页面使用图像左侧的图表 作为起始图(在 k = 0 时的第一次迭代之前)，然后显示剩余的迭代(k = 1 等)，但它没有解释节点之间数字的重要性以及如何计算这些数字。比如起始图中k=0的时候，为什么1和3之间的边上有一个-2，为什么2和3之间的边上有一个3，这些是怎么计算的？

此外，当 k = 2 时，维基百科页面说，

The path [4,2,3] is not considered, because [2,1,3] is the shortest path encountered so far from 2 to 3.

为什么 [2,1,3] 比 [4,2,3] 短？

Answer 1

边缘上的数字只是权重。它是输入的一部分。该算法不计算它们。

[2, 1, 3] 不短于 [4, 2, 3]。不过，它比 [2, 3] 短。这是唯一重要的事情。