floyd warshall 中节点之间的距离

Question

Thiswikipedia page explains the Floyd Warshall algorithm to find the shortest path between nodes in a graph. The wikipedia page uses the graph on the left of the image 作为起始图（在 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] 短。这是唯一重要的事情。