floyd算法 矩阵 理解_floyd算法的概念模型_探求Floyd算法的动态规划本质(2)

那如何利用一个二维数组来实现滚动数组，以减小空间复杂度呢？

上图是使用滚动数组，在第k阶段，计算d[i][j]时的情况。此时，由于使用d[][]这个二维数组作为滚动数组，在各个阶段的计算中被重复使用，因此数组中表示阶段的那一维也被取消了。在这图中，白色的格子，代表最新被计算过的元素（即第k阶段的新值），而灰色的格子中的元素值，其实保存的还是上一阶段（即第k-1阶段）的旧值。因此，在新的d[i][j]还未被计算出来时，d[i][j]中保存的值其实就对应之前没有用滚动数组时d[k-1][i][j]的值。此时，动态转移方程在隐藏掉阶段索引后就变为：

d[i][j] = min(d[i][j], d[i][k]+d[k][j])（k,i,j∈[1,n]）

赋值号左侧d[i][j]就是我们要计算的第k阶段是i和j之间的最短路径长度。在这里，需要确保赋值号右侧的d[i][j], d[i][k]和d[k][j]的值是上一阶段（k-1阶段）的值。前面已经分析过了，在新的d[i][j]算出之前，d[i][j]元素保留的值的确就是上一阶段的旧值。但至于d[i][k]和d[k][j]呢？我们无法确定这两个元素是落在白色区域（新值）还是灰色区域（旧值）。好在有这样一条重要的性质，dp[k-1][i][k]和dp[k-1][k][j]是不会在第k阶段改变大小的。也就是说，凡是和k节点相连的边，在第k阶段的值都不会变。如何简单证明呢？我们可以把j=k代入之前的d[k][i][j]=min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])方程中，即：

d[k][i][k]

= min(d[k-1][i][k], d[k-1][i][k]+d[k-1][k][k])

= min(d[k-1][i][k], d[k-1][i][k]+0)

= d[k-1][i][k]

也就是说在第k-1阶段和第k阶段，点i和点k之间的最短路径长度是不变的。相同可以证明，在这两个阶段中，点k和点j之间的的最短路径长度也是不变的。因此，对于使用滚动数组的转移方程d[i][j] = min(d[i][j], d[i][k]+d[k][j])来说，赋值号右侧的d[i][j], d[i][k]和d[k][j]的值都是上一阶段（k-1阶段）的值，可以放心地被用来计算第k阶段时d[i][j]的值。

利用滚动数组改写后的floyd算法代码如下：

1

2

3

4

5

6

void floyd() {

for(int k = 1; k <= n; k++)

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

}

因此，通过这篇文章的分析，我们可以发现，Floyd算法的的确确是一种典型的动态规划算法；理解floyd算法，也可以帮助我们进一步理解动态规划思想。

转载?p=81

以上就是关于floyd算法的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-7522-2.html