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

你是否正在寻找关于floyd算法的内容？让我把最有价值的东西奉献给你：

Floyd–Warshall（简称Floyd算法）是一种著名的解决任意两点间的最短路径（All Paris Shortest Paths，APSP）的算法。从表面上粗看，Floyd算法是一个非常简单的三重循环，而且纯粹的Floyd算法的循环体内的语句也十分简洁。我认为，正是由于“Floyd算法是一种动态规划（Dynamic Programming）算法”的本质，才导致了Floyd算法如此精妙。因此，这里我将从Floyd算法的状态定义、动态转移方程以及滚动数组等重要方面，来简单剖析一下图论中这一重要的基于动态规划的算法——floyd算法。

在动态规划算法中，处于首要位置、且也是核心理念之一的就是状态的定义。在这里，把d[k][i][j]定义成：

“只能使用第1号到第k号点作为中间媒介时，点i到点j之间的最短路径长度。”

图中共有n个点，标号从1开始到n。因此，在这里，k可以认为是动态规划算法在进行时的一种层次，或者称为“松弛操作”。d[1][i][j]表示只使用1号点作为中间媒介时，点i到点j之间的最短路径长度；d[2][i][j]表示使用1号点到2号点中的所有点作为中间媒介时，点i到点j之间的最短路径长度；d[n-1][i][j]表示使用1号点到(n-1)号点中的所有点作为中间媒介时，点i到点j之间的最短路径长度d[n][i][j]表示使用1号到n号点时，点i到点j之间的最短路径长度。有了状态的定义之后，就可以根据动态规划思想来构建动态转移方程。

动态转移的基本思想可以认为是建立起某一状态和之前状态的一种转移表示。按照前面的定义，d[k][i][j]是一种使用1号到k号点的状态，可以想办法把这个状态通过动态转移，规约到使用1号到(k-1)号的状态，即d[k-1][i][j]。对于d[k][i][j]（即使用1号到k号点中的所有点作为中间媒介时，i和j之间的最短路径），可以分为两种情况：（1）i到j的最短路不经过k；（2）i到j的最短路经过了k。不经过点k的最短路情况下，d[k][i][j]=d[k-1][i][j]。经过点k的最短路情况下，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。因此，综合上述两种情况，便可以得到floyd算法的动态转移方程：

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

最后，d[n][i][j]就是所要求的图中所有的两点之间的最短路径的长度。在这里，需要注意上述动态转移方程的初始（边界）条件，即d[0][i][j]=w(i, j)，也就是说在不使用任何点的情况下（“松弛操作”的最初），两点之间最短路径的长度就是两点之间边的权值（若两点之间没有边，则权值为INF，且我比较偏向在floyd算法中把图用邻接矩阵的数据结构来表示，因为便于操作）。当然，还有d[i][i]=0（i∈[1,n]）。

这样我们就可以编写出最为初步的floyd算法代码：

1

2

3

4

5

6

7

8

9

10

11

12

void floyd_original() {

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

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

d[0][i][j] = graph[i][j];

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

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

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

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

}

}

}

}

几乎所有介绍动态规划中最为著名的“0/1背包”问题的算法书籍中，都会进一步介绍利用滚动数组的技巧来进一步减少算法的空间复杂度，使得0/1背包只需要使用一维数组就可以求得最优解。而在各种资料中，最为常见的Floyd算法也都是用了二维数组来表示状态。那么，在floyd算法中，是如何运用滚动数组的呢？

再次观察动态转移方程d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])，可以发现每一个第k阶段的状态（d[k][i][j]），所依赖的都是前一阶段（即第k-1阶段）的状态（如d[k-1][i][j]，d[k-1][i][k]和d[k-1][k][j]）。

上图描述了在前面最初试的floyd算法中，计算状态d[k][i][j]时，d[k-1][][]和d[k][][]这两个二维数组的情况（d[k-1][][]表示第k-1阶段时，图中两点之间最短路径长度的二维矩阵；d[k][][]表示第k阶段时，图中两点之间最短路径长度的二维矩阵）。红色带有箭头的有向线段指示了规划方向。灰色表示已经算过的数组元素，白色代表还未算过的元素。由于d[k-1][][]和d[k][][]是两个相互独立的二维数组，因此利用d[k-1][i][j]，d[k-1][i][k]和d[k-1][k][j]（皆处于上方的二维数组中）来计算d[k][i][j]时没有任何问题，。

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