algorithm - Floyd Warshall 算法在以下情况下的工作原理

Question

假设我有 9 个顶点。所以我有 9x9 解决方案矩阵和

matrix[6,0] = infinity, 
matrix[6,9]=1, 
matrix[9,0]=1

现在算法的工作原理如下:

for k 1 to 9
    for i 1 to 9
        for j 1 to 9

现在假设k=6

所以对于 matrix[5,0] 比较将在 (matrix[5,6]+matrix[6,0]) 和 matrix[ 5,0] 在这种情况下 matrix[6,0] = infinity 所以 matrix[5,0] 将是值。

但是当k=9

matrix[6,0] 变成 => matrix[6,9] + matrix[9,0] = 1 + 1 = 2

但是现在没有办法更新matrix[5,0]。

这是我的理解。那么算法在这种情况下是如何工作的。

Answer 1

如果你的循环从 0 开始，其他值都是 0 除了 matrix[6]{0,9}和 matrix[9][0]然后
matrix[6][0]将从matrix[6][1]+matrix[1][0]更新
matrix[6][9]将从matrix[6][1]+matrix[1][9]更新
matrix[9][0]将从matrix[9][1]+matrix[1][0]更新

您不需要更新 matrix[5][0]因为它已经是 0 了？

基本上当你有 K loop k 中的值这意味着您将要添加另一条边以及从 (i->j) 出发的所有可能方式使用 edges(1->K-1) 更新.
然后插入另一条边 K然后你再次检查是否有任何方式可以从(i->j)开始以更便宜的方式使用这个优势。所以你写matrix[i][j]=min(matrix[i][j],matrix[i][k]+matrix[k][j])