假设我有 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]。
这是我的理解。那么算法在这种情况下是如何工作的。
最佳答案
如果你的循环从 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])
关于algorithm - Floyd Warshall 算法在以下情况下的工作原理，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58477338/