美文网首页
多源点最短路径:弗洛伊德算法与动态规划

多源点最短路径:弗洛伊德算法与动态规划

作者: 薄荷色草地芬芳像风没有形状 | 来源:发表于2021-08-31 08:31 被阅读0次

        在数据结构的学习中,关于图的算法有诸如迪杰斯特拉算法,Bellman-Ford算法等,然而之前只是为了应付考试或者简单学习算法流程,所以总是学一遍,忘一遍,不深刻理解它是怎么来的,就总也记不住,反正我是这样。所以,今天重新学习了一下多源点最短路径算法:弗洛伊德算法,并从动态规划的角度重新理解它。

        简单回顾一下动态规划思想,动态规划常用于子问题重叠的情况,当不同的子问题有公共的子子问题时(子问题的求解递归进行),无脑递归它会反复求解那些重复的子问题,造成计算资源的浪费。而动态规划就是将子子问题只求解一次,从而无需重复计算。它的一个最基本特征是该问题会用到子问题的最优解,子问题的又会用到子子问题的最优解。

        看一个简单的例子:先描述一下我们要解决的问题,求出该图中所有节点之间的最短距离。当然我们的目的是寻找让计算机解决这个问题的通用的办法,我们用眼睛看当然很容易,但当图规模特别大时,就得靠计算机了。

为了便于表示,我们可以用二维矩阵来表示各个节点之间的距离。

这是初始情况,在不经过任何节点的情况下,各个节点之间的距离。之后所有的操作都在这个矩阵上进行。

        再来说说如何用动态规划来解决这个问题:假如要求两节点Vi和Vj之间的最短距离,假设还有k个其它节点。这个问题的子问题是:除去第k个节点,i和j之间经过k和不经过k两个子问题。此时假设已求得包含了前k-1个中间节点的最短路径。经过k的最短距离就是Dik+Dkj;不经过k的最短距离就是Dij,这里的D都是在利用了k-1个中间节点后的求得的最短距离。所以只要在这两个子问题中挑出最小值即可。这时子子问题产生了,利用k-1个中间节点的i和j之间,i和k之间,k和j之间的距离怎么求呢。这时就可以推给图包含前k-2个中间节点的最短距离,有点像数列中的递推公式。这时问题的最优解就利用了子问题的最优解,这便是动态规划问题都要满足的最优子结构。

如下便是多源点最短路径的递推式:

我们的思路是自顶向下递推,而我们求解问题的思路便是自底向上求解,因为自底向上的话我们可以将子问题的最优解记录下来,求解上层问题的时候直接查就行了。

再回到开始的实例,我们以节点1,2,3的顺序开始包含:

初始包含0个节点:

包含节点1:

这里举个例子3到2的距离是如何从无穷大更新到7的:此时k=1,也就是在包含k-1=0个节点的基础上(初始矩阵)计算,

d(3,2)=无穷大;d(3,1)+d(1,2)=3+4=7;选择较小的7更新矩阵。(注意这里的3+4不是从图上看的,而是在C0那个矩阵里找的,因为计算机可不会看图,而且矩阵的9个值都要挨个算一遍,只不过有的不需要更新)。

然后包含节点2:

这里看一下1到3的最短距离是怎么更新到6的:此时k=2,也就是在包含k-1=1个节点的基础(即矩阵C1)上计算,d(1,3)=11;d(1,2)+d(2,3)=4+2=6;选择更小的6更新矩阵。同样这里的值都是从C1矩阵中找的,这里C1就是C2的子问题。求解C2利用的子问题的最优解。

然后包含节点3:

此时这个矩阵中便包含了任意节点之间的最短距离,在问题规模特别大时,计算机可以利用这个方法很快求得全局的最优解。这便是多源点最短路径的佛洛依德算法,下面给出该算法的伪代码。

C={dij}        // 初始化矩阵

for k = 1 to n

        for i = 1 to n

                for j = 1 to n

                        dij = min(dij, dik + dkj)

return C

该算法的时间复杂度是O(n^3),该算法不仅代码简洁,而且是一个很巧妙很棒的算法,可以帮助我们快速算得图上任意两个节点的最短距离,在通信路由领域用途广泛。

2020-11-10 15:31 上传

相关文章

  • 图-最短路径-弗洛伊德算法

    多源点最短路径-弗洛伊德算法(Floyd) 求所有顶点到所有顶点的最短路径,而迪杰斯特拉是求单源点到所有顶点的最短...

  • Floyd 算法

    Floyd 算法 简介 Floyd 算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径...

  • 多源点最短路径:弗洛伊德算法与动态规划

    在数据结构的学习中,关于图的算法有诸如迪杰斯特拉算法,Bellman-Ford算法等,然而之前只是为了应付考试或者...

  • floyd算法解析

    floyd算法可求得多源点间的最短路径算法使用动态规划求解: 状态转移方程 dp[i][j][k]=min(dp[...

  • 算法实验四-动态规划

    1.多段图中的最短路径问题【问题描述】建立一个从源点S到终点T的多段图,设计一个动态规划算法求出从S到T的最短路径...

  • (C/C++)动态规划:多段图最短路径、有向无环图最短路径、最长

    多段图的最短路径问题 建立一个从源点S到终点T的多段图,设计一个动态规划算法求出从S到T的最短路径值,并输出相应的...

  • [算法](00001) Floyed

    介绍 利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法 思路 遍历所有地点(一层循环),判断该地点是否...

  • 最短路径 之 Floyd 算法

    • 最短路径 之 Dijkstra 算法• 最短路径 之 Bellman 算法 Floyd算法是基于一种动态规划的...

  • 最短路径算法

    最短路径算法可以分为两类:单源最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径。多源最短路径问题:求任...

  • 第三章 路径分析算法——基于Floyd算法的路径分析

    3.2 基于Floyd算法的路径分析 Floyd算法是一种用于在已知给定的加权图中求多源点之间最短路径的算法。它于...

网友评论

      本文标题:多源点最短路径:弗洛伊德算法与动态规划

      本文链接:https://www.haomeiwen.com/subject/jgnniltx.html