Floyed理解「建议收藏」

Floyed理解「建议收藏」Floyed理解 Floyd算法的本质是动态规划,其转移方程为:f(k,i,j)=min(f(k-1,i,j),f(k-1,i,k)+f(k-1,k,j))。f(k-1,i,j)表示经过前k-1个点f(k-1,i,k)+f(k-1,k,j)表示经过k这个点f(k,i,j)表示路径除开起点i与终点j,只经过前k个点中的某些点,从i到j的最小值。计算这个值只需要考…

大家好,又见面了,我是你们的朋友全栈君。

Floyed理解

Floyed理解「建议收藏」

 

Floyd算法的本质是动态规划,其转移方程为:f(k,i,j) = min( f(k-1,i,j), f(k-1,i,k)+f(k-1,k,j) )

f(k-1,i,j)表示经过前k-1个点

f(k-1,i,k)+f(k-1,k,j)表示经过k这个点

f(k,i,j)表示路径除开起点i与终点j,只经过前k个点中的某些点,从i到j的最小值。

计算这个值只需要考虑两种情况:最短路经过k,和最短路不经过k(那么就经过前k-1个点中的某些点)。

由于k要从k-1转移而来,自然k为最外层的循环。而经过状态压缩(类似于背包问题)后,就变成了我们熟悉的f(i,j) = min( f(i,j), f(i,k)+f(k,j) )了。

 

 

接下来,是Floyd算法的更新过程。归纳一下它的更新过程,其实就是,每一次尝试在每一对节点Vv和Vw之间插入一个节点Vk,如果插入节点后,可以使得Vv和Vw之间的路径变短,那么进行一次更新,否则不更新。

那么,为什么按照这样的规则更新可以找到每对节点间的最短路径呢?我在这里举个例子说明一下,应该就可以把这个问题解释清楚了。假设我们事先已经知道从节点V2到V5之间的最短路径是:V2→V4→V9→V7→V5。

第一步,在初始化过程中,我们获得了(*D)[2][9]、(*D)[9][5]、(*D)[2][5]以及(*P)[2][9]、(*P)[9][5]、(*P)[2][5]的初始值。

第二步,按照Floyd算法进行迭代,迭代到k等于4时,我们会发现在V2和V9之间插入V4之后,V2和V9之间的路径长度达到了史上最低点,(*D)[2][9]更新为(*D)[2][4]+(*D)[4][9],(*P)[2][9]更新为4。而且在之后的迭代中都不会出现更短的路径,所以(*D)[2][9]和(*P)[2][9]在之后的迭代中都不会发生改变。

第三步,迭代到k等于7时,V9和V5之间的路径长度达到了史上最低点,(*D)[9][5]更新为(*D)[9][7]+(*D)[7][5],(*P)[9][5]更新为7,此后不再改变。

第四步,迭代到k等于9时,V2和V5之间的路径长度达到了史上最低点,(*D)[2][5]更新为(*D)[2][9]+(*D)[9][5],(*P)[2][5]更新为9,此后不再改变。这样也就找到了V2和V5之间的最短路径。

现在,我们算出了V2和V5之间的最短路径的长度,但是,怎样找到这条路径的轨迹呢?其实就是根据*P来推断。以上面的例子为例,如果我们要打印V2和V5之间的最短路径的轨迹。首先我们知道(*P)[2][5]=9,初步确定轨迹为V2→V9→V5。根据(*P)[2][9]=4且(*P)[9][5]=7,初步确定轨迹为V2→V4→V9→V7→V5。根据(*P)[2][4]=2,(*P)[4][9]=4,(*P)[9][7]=9,(*P)[7][5]=7,我们可以确定没有新的节点需要加入,所以确定最终的轨迹为V2→V4→V9→V7→V5。

 

Floyed题目推荐:

【P1119】灾后重建 – 洛谷
https://www.luogu.org/problem/show?pid=1119

【P1078】文化之旅 – 洛谷
https://www.luogu.org/problem/show?pid=1078

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/148322.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • java socket详解_Java Socket 编程原理及教程「建议收藏」

    java socket详解_Java Socket 编程原理及教程「建议收藏」原标题:JavaSocket编程原理及教程对于JavaSocket编程而言,有两个概念,一个是ServerSocket,一个是Socket。服务端和客户端之间通过Socket建立连接,之后它们就可以进行通信了。首先ServerSocket将在服务端监听某个端口,当发现客户端有Socket来试图连接它时,它会accept该Socket的连接请求,同时在服务端建立一个对应的Socket与之进行通…

    2022年10月18日
    1
  • docker下载安装教程_centos一键安装docker

    docker下载安装教程_centos一键安装docker前言Docker提供轻量的虚拟化,你能够从Docker获得一个额外抽象层,你能够在单台机器上运行多个Docker微容器,而每个微容器里都有一个微服务或独立应用,例如你可以将Tomcat运行在一个D

    2022年7月31日
    2
  • Maven 打包命令

    Maven 打包命令cmd命令:–>跳过测试mvn clean -Dmaven.test.skip=true package -P prod运行:java-jarxxx.jarlinux下运行jarLinux运行jar包命令如下:方式一:java -jar XXX.jar特点:当前ssh窗口被锁定,可按CTRL+C打断程序运行,或直接关闭窗口,程序退出那如何让窗口不锁定?方式二:java -jar …

    2022年6月12日
    23
  • 零基础学Java(3)运算符

    零基础学Java(3)运算符运算符运算符用于连接值。Java提供了一组丰富的算术和逻辑运算符以及数学函数。算术运算符在Java中,使用算术运算符+、-、*、/表示加、减、乘、除运算。当参与/运算的两个操作数都是整数时,表示

    2022年7月31日
    4
  • java json转换为对象_Java list map

    java json转换为对象_Java list mapjson转map的六种方式

    2022年9月8日
    0
  • mapminmax的用法

    mapminmax的用法几个要说明的函数接口:[Y,PS]=mapminmax(X)[Y,PS]=mapminmax(X,FP)Y=mapminmax(‘apply’,X,PS)X=mapminmax(‘reverse’,Y,PS)用实例来讲解,测试数据x1=[124],x2=[523];>>[y,ps]=mapminmax(x1)y=  -1

    2022年6月17日
    106

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号