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] 短?
最佳答案
边缘上的数字只是权重。它是输入的一部分。该算法不计算它们。
[2, 1, 3] 不短于 [4, 2, 3]。不过,它比 [2, 3] 短。这是唯一重要的事情。
关于algorithm - floyd warshall 中节点之间的距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41087141/