我已经阅读并搜索了 Floyd Warshall 算法，我想我理解它。但是在我在“算法简介（Thomas H. Cormen 的书）”一书中读到的示例中，我堆叠在一个点上。我很困惑。这是书中相同的图片。我的问题在最后一步，即 π(5)。这是示例：http:
//integrator-crimea.com/images/fig653_01_0.jpg
I think the first row of π(5) must be :
NIL 5 5 5 1
However it is written in the book :
NIL 3 4 5 1
有人可以解决我上面的困惑吗？书上写错了吗？
让我们写成D_4(1,3)距离矩阵 D(4) 中的第 1 行第 3 列。
如果D_5(1,2)=1被解释by Pi_5(1,2)=3（即从 1 到 2 的最短路径经过 3），我们希望D_5(1,2) = D_4(1,3) + D_4(3,2). 然而，D_5(1,2) = 1 but D_4(1,3) + D_4(3,2) = -1 + 4 = 3. 所以Pi_5(1,2)=3是不正确的。
您的替代值Pi_5(1,2)=5 is正确，因为1 = D_5(1,2) = D_4(1,5) + D_4(5,2) = -4 + 5.
所以你说 Pi(5) 的第一行中的第二个值应该是 5，而不是 3 是正确的。我没有检查其他值，但我认为你对这些值也是正确的。