(floyd)佛洛伊德算法

  • 时间:
  • 浏览:0
  • 来源:5分3D官方_极速5分排列5

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]

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

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

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

3

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

5

3

d[k][i][k]

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

6

在动态规划算法中,所处首要位置、且也是核心理念之一的却说 状况的定义。在这里,把d[k][i][j]定义成:

8

2

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

Floyd–Warshall(简称Floyd算法)是并都在著名的外理任意两点间的最短路径(All Paris Shortest Paths,APSP)的算法。从下皮 上粗看,Floyd算法是另4个非常简单的三重循环,因此纯粹的Floyd算法的循环体内的句子也十分简洁。我认为,正是因此“Floyd算法是并都在动态规划(Dynamic Programming)算法”的本质,才因为了Floyd算法没办法 精妙。因此,这里我将从Floyd算法的状况定义、动态转移方程以及滚动数组等重要方面,来简单剖析一下图论中这名重要的基于动态规划的算法——Floyd算法。

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

            }

4

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

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

void floyd_original() {

没办法 大伙儿儿就还都可否 编写出最为初步的Floyd算法代码:

10

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

12

}

1

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

}

4

也却说 说在第k-1阶段和第k阶段,点i和点k之间的最短路径长度是不变的。相同还都可否 证明,在这另4个阶段中,点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]的值。

11

上图是使用滚动数组,在第k阶段,计算d[i][j]时的状况。此时,因此使用d[][]这名二维数组作为滚动数组,在各个阶段的计算中被重复使用,因此数组中表示阶段的那一维也被撤回了。在这图中,白色的格子,代表最新被计算过的元素(即第k阶段的新值),而灰色的格子中的元素值,着实保存的还是上一阶段(即第k-1阶段)的旧值。因此,在新的d[i][j]还未被计算出来时,d[i][j]中保存的值着实就对应却说 没办法 用滚动数组时d[k-1][i][j]的值。此时,动态转移方程在隐藏掉阶段索引后就变为:

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

图中共有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之间的最短路径长度。有了状况的定义却说 ,就还都可否 根据动态规划思想来构建动态转移方程。

2

9

                d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][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算法的动态转移方程:

“没办法 使用第1号到第k号点作为后边媒介时,点i到点j之间的最短路径长度。”

        }

1

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

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

因此,通过这篇文章的分析,大伙儿儿还都可否 发现,Floyd算法的的确确是并都在典型的动态规划算法;理解Floyd算法,也还都可否 帮助大伙儿儿进一步理解动态规划思想。

void floyd() {

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

6

    }

上图描述了在前面最初试的Floyd算法中,计算状况d[k][i][j]时,d[k-1][][]和d[k][][]这另4个二维数组的状况(d[k-1][][]表示第k-1阶段时,图中两点之间最短路径长度的二维矩阵;d[k][][]表示第k阶段时,图中两点之间最短路径长度的二维矩阵)。红色中有 箭头的有向线段指示了规划方向。灰色表示因此算过的数组元素,白色代表还未算过的元素。因此d[k-1][][]和d[k][][]是另4个相互独立的二维数组,因此利用d[k-1][i][j],d[k-1][i][k]和d[k-1][k][j](皆所处后边的二维数组中)来计算d[k][i][j]时没办法 任何什么的大问题。

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

几乎所有介绍动态规划中最为著名的“0/1背包”什么的大问题的算法书籍中,不会进一步介绍利用滚动数组的技巧来进一步减少算法的空间僵化 度,使得0/1背包只前要使用一维数组就还都可否 求得最优解。而在各种资料中,最为常见的Floyd算法也都在用了二维数组来表示状况。没办法 ,在Floyd算法中,是何如运用滚动数组的呢?

5

赋值号左侧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]呢?大伙儿儿无法选择这另4个元素是落在白色区域(新值)还是灰色区域(旧值)。好在有没办法 每根重要的性质,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])方程中,即:

那何如利用另4个二维数组来实现滚动数组,以减小空间僵化 度呢?

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

7