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，则矩阵[6] [0]除外然后matrix[6][0] will be updated from matrix[6][1]+matrix[1][0]matrix[6][9] will be updated from matrix[6][1]+matrix[1][9]matrix[9][0] will be updated from matrix[9][1]+matrix[1][0]基本上，当您在K中具有loop k值时，这意味着您将要添加另一条边，并且使用(i->j)更新了从edges(1->K-1)开始的所有可能方式。然后插入另一条边K，然后再次检查是否有任何便宜的方法可以使用[c0]从该边离开(i->j)。所以你写matrix[i][j]=min(matrix[i][j],matrix[i][k]+matrix[k][j])