多源最短路径算法 -- 弗洛伊德(Floyd)算法

1. 简介

        Floyd算法,全名为Floyd-Warshall算法,亦称弗洛伊德算法或佛洛依德算法是一种用于寻找给定加权图中所有顶点对之间的最短路径的算法。这种算法以1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德的名字命名。

2. 核心思想

        通过考虑图中所有可能的中转点,逐步更新两点间的最短路径长度和路径信息,直至找到最终的最短路径。有的人也称之为插点法。

3. 图解

3.1 初始化

初始化:设置图的邻接矩阵dict,其中dict[i][j]表示顶点i到顶点j的直接路径权重;如果两顶点不直接相连,则设为无穷大INF。

3.2  更新最短路径

更新最短路径:把每个节点当作是中转节点,更新矩阵中的距离。

通过中间顶点 k 从顶点 i 到顶点 j 的距离 小于 直接从顶点 i 到顶点 j 的距离,更新 dist[i][j] = dist[i][k] + dist[k][j]

把0作为中转节点,此时表中黄色部分是不需要改的(都是从0出发或是直接到0的距离),

当更新 dict[1][2]也就是1 -> 2 时,需判断 1 -> 0 和 0 -> 2 的和是否比直达的1 -> 2更小。

若路径中有INF就无需更新,比如此时1 -> 0 就是INF,表示1 -> 2 以 0 作为中转点时不可能比 1 -> 2 直达的更小,所以此时不需要更新。

更新完 0作为中转节点时 数组为:

更新完 1作为中转节点时 数组为:

 

 更新完 2作为中转节点时 数组为:

 更新完 3作为中转节点时 数组为:

3.3 结果

        最终结果的数组中就是点到点的最短路径。

4. 代码实现

        定义了一个4x4的图,其中INF表示两个顶点之间没有直接相连的边。然后调用floyd方法计算所有顶点对之间的最短路径,并输出结果。

public class Floyd {private static final int INF = Integer.MAX_VALUE; public static void floyd(int[][] graph) {int n = graph.length; // 获取图的顶点数int[][] dist = new int[n][n]; // 初始化矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dist[i][j] = graph[i][j]; }}// 使用Floyd算法计算所有顶点之间的最短路径for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] != INF && dist[k][j] != INF&& dist[i][k] + dist[k][j] < dist[i][j]) { // 更新i到j的最短路径dist[i][j] = dist[i][k] + dist[k][j];}}}}// 输出所有顶点之间的最短路径for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(dist[i][j] + " ");}System.out.println();}}public static void main(String[] args) {int[][] graph = {{0,   5  , 3  , 10 },{INF, 0  , 3  , INF},{5  , INF, 0  , 1  },{INF, INF, 4  , 0  }};floyd(graph); }
}

5. floyd算法和Dijkstra算法的区别

        Floyd算法和Dijkstra算法都是计算图中顶点之间最短路径的著名算法,但它们的应用场景、原理和性能存在显著差异。具体分析如下:

  • 应用场景

    • Dijkstra算法:适用于单源最短路径问题,即从单个源点到其他所有点的最短路径。它不能处理具有负权边的图。
    • Floyd算法:用于求解任意顶点对(多源最短路径问题)的最短路径,可以处理负权边,但不能处理包含负权回路的图。
  • 算法原理

    • Dijkstra算法:基于贪心策略,每次从未确定的顶点中选择一个距离源点最近的顶点,然后更新其邻接顶点的距离。该算法需要使用优先队列来选择下一个顶点,并且初始时除源点外的所有顶点的距离都设置为无穷大。
    • Floyd算法:通过动态规划的方式,利用三层嵌套循环来计算所有顶点对之间的最短路径。算法的基本操作是比较(u,k) + (k,v)与(u,v)的长度,并据此更新(u,v)的长度。
  • 时间复杂度

    • Dijkstra算法:使用优先队列优化后的时间复杂度是O((V+E) log V),其中V是顶点数,E是边数。如果使用邻接矩阵实现且没有优化,复杂度会是O(V^2)。
    • Floyd算法:时间复杂度为O(V^3),因为算法需要三层循环遍历所有顶点对和可能的中间顶点。
  • 额外功能

    • Dijkstra算法:可以输出从源点到各顶点的最短路径。
    • Floyd算法:可以输出任意两个顶点间的最短路径及其长度。

        总之,Dijkstra算法适合解决单源最短路径问题,尤其是在没有负权边的情况下,而Floyd算法适合解决所有顶点对之间的最短路径问题,尽管它可以处理负权边的情况,却不能容忍负权回路的存在。

        

6. 总结 

        总的来说,Floyd算法是一种计算图中所有顶点对之间最短路径的动态规划算法,它能够处理包含负权边的图,但不允许存在负权回路。适用于小型到中等规模稠密图的算法,尤其是在需要全局最短路径信息时。对于大型稀疏图或者单源最短路径问题,其他算法如Dijkstra算法可能更加合适。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/348665.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从报名到领证:软考初级【信息系统运行管理员】报名考试全攻略

本文共计9991字&#xff0c;预计阅读33分钟。包括七个篇章&#xff1a;报名、准考证打印、备考、考试、成绩查询、证书领取及常见问题。 一、报名篇 报名条件要求&#xff1a; 1.凡遵守中华人民共和国宪法和各项法律&#xff0c;恪守职业道德&#xff0c;具有一定计算机技术…

centos7.9部署k8s的几种方式

文章目录 一、常见的k8s部署方式1、使用kubeadm工具部署2、基于二进制文件的部署方式3、云服务提供商的托管 Kubernetes 服务4、使用容器镜像部署或自动化部署工具 二、使用kubeadm工具部署1、硬件准备&#xff08;虚拟主机&#xff09;2、环境准备2.1、所有机器关闭防火墙2.2、…

sizeof和strlen

1.sizeof和strlen的对比 1.1sizeof sizeof是计算变量所占内存空间大小的&#xff0c;单位是&#xff1a;字节 如果操作数是类型的话&#xff0c;计算的是使用类型创建的变量所占内存空间的大小。 sizeof只关注占用内存空间的大小&#xff0c;不在乎内存中存放的是什么数据 …

vuInhub靶场实战系列--Kioptrix Level #4

免责声明 本文档仅供学习和研究使用,请勿使用文中的技术源码用于非法用途,任何人造成的任何负面影响,与本人无关。 目录 免责声明前言一、环境配置1.1 靶场信息1.2 靶场配置 二、信息收集2.1 主机发现2.1.1 netdiscover2.1.2 arp-scan主机扫描 2.2 端口扫描2.3 指纹识别2.4 目…

CBoard开源数据可视化工具

CBoard开源数据可视化工具 文章目录 CBoard开源数据可视化工具介绍资源列表基础环境一、安装JDK二、安装Maven2.1、安装Maven2.2、配置Maven 三、安装Tomcat8四、安装MySQL5版本4.1、安装相关依赖4.2、二进制安装4.3、设定配置文件4.4、配置systemcatl方式启动4.5、访问MySQL数…

韩国版AlphaFold?深度学习模型AlphaPPIMd:用于蛋白质-蛋白质复合物构象集合探索

在生命的舞台上&#xff0c;蛋白质扮演着不可或缺的角色。它们是生物体中最为活跃的分子&#xff0c;参与细胞的构建、修复、能量转换、信号传递以及无数关键的生物学功能。同时&#xff0c;蛋白质的结构与其功能密切相关&#xff0c;而它们的功能又通过与蛋白质、多肽、核苷酸…

新疆在线测宽仪配套软件实现的9大功能!

在线测宽仪可应用于各种热轧、冷轧板带材的宽度尺寸检测&#xff0c;材质不限&#xff0c;木质、钢制、铁质、金属、纸质、塑料、橡胶等都可以进行无损非接触式的检测&#xff0c;在各式各样的产线应用中&#xff0c;有些厂家&#xff0c;需要更加详尽完备的分析信息&#xff0…

[2024-06]-[大模型]-[DEBUG]- ollama webui 11434 connection refused

报错&#xff1a;host.docker.internal:11434 ssl:default [Connection refused] 将/etc/systemd/system/ollama.service中加上如下红框两行 Environment"OLLAMA_HOST0.0.0.0" Environment"OLLAMA_ORIGINS*"然后 systemctl daemon-reload systemctl rest…

vue3 监听器,组合式API的watch用法

watch函数 在组合式 API 中&#xff0c;我们可以使用 watch 函数在每次响应式状态发生变化时触发回调函数 watch(ref,callback&#xff08;newValue,oldValue&#xff09;&#xff0c;option:{}) ref:被监听的响应式量&#xff0c;可以是一个 ref (包括计算属性)、一个响应式…

SpringMVC:拦截器(Interceptor)

1. 简介 拦截器&#xff08;Interceptor&#xff09;类似于过滤器&#xff08;Filter&#xff09; Spring MVC的拦截器作用是在请求到达控制器之前或之后进行拦截&#xff0c;可以对请求和响应进行一些特定的处理。拦截器可以用于很多场景下&#xff1a; 1. 登录验证&#xf…

修改版的VectorDBBench更好用

原版本VectorDBBench的几个问题 在这里就不介绍VectorDBBench是干什么的了&#xff0c;上官网即可。 1.并发数设置的太少 2.测试时长30秒太长 3.连接milvus无用户和密码框&#xff0c;这个是最大的问题 4.修改了一下其它参数 由于很多网友发私信问一些milvus的相关技术问…

php redis分布式锁

一&#xff0c;概念 在PHP中实现分布式锁通常可以使用数据库、缓存系统&#xff08;如Redis&#xff09;或者其他中央存储系统来保证在分布式系统中的数据一致性与同步。秒杀下单、抢红包等等业务场景&#xff0c;都需要用到分布式锁。 常规方案大概有七中 方案一&#xff1a;…

defer+recover机制处理错误

问题&#xff1a;多个协程工作&#xff0c;其中一个协程出现panic&#xff0c;导致程序崩溃 解决办法&#xff1a;利用deferrecover捕获panic进行处理&#xff0c;即使协程出现错误&#xff0c;主线程仍然不受影响可以继续执行 package mainimport ("fmt""tim…

23种设计模式之组合模式

组合模式 1、定义 组合模式&#xff1a;组合多个对象形成树状结构以表示具有部分-整体关系的层次结构。组合模式让客户端可以统一对待单个对象和组合对象 2、组合模式结构 Component&#xff08;抽象构件&#xff09;&#xff1a;可以是接口或抽象类&#xff0c;为叶子构件…

JAVA:通过电信ctg.ag.sdk从电信物联平台AIOT获取设备上报数据的简单示例

一、问题场景 物联设备比如NB设备通过NB协议将数据传到电信平台后&#xff0c;我们的应用服务如何从电信平台获取可用的上报数据。以下通过电信开发者平台提供的SDK来简单演示下整个过程。 二、使用电信 SDK进行开发 电信AIOT物联平台提供了两种方式获取平台数据&#xff0c…

Mac 下载并激活IDEA

1.https://3.jetbra.in 打开这个网站,点击第一个网速比较快的连接 2.在新页面顶部有一个蓝色的下载链接文字< jetbra.zip(20220801) >点击下载 3.步骤2打开的页面不要关闭后面还有用 4.在idea官网下载idea对应的版本 https://www.jetbrains.com/idea/download/other.htm…

视频格式转换avi格式怎么弄?分享视频转换方法

视频格式转换avi格式怎么弄&#xff1f;AVI作为一种广泛支持的视频格式&#xff0c;能够在多种设备和播放器上顺畅播放&#xff0c;确保我们的视频内容能够无障碍地分享给朋友或上传至各大平台。其次&#xff0c;AVI格式通常具有较好的兼容性&#xff0c;能够避免格式转换过程中…

【方法】Word文档如何添加“打开密码”?

Word文档是很常用的办公文档&#xff0c;对于重要的文档&#xff0c;不想被他人随意查看&#xff0c;或者只有指定的人可以查看&#xff0c;我们可以给Word文档设置密码保护&#xff0c;这样只有知道密码的人才可以打开文档。 下面分享两种Word文档添加“打开密码”的方法&…

SAP 价格金额信息控制

1)migo / mb51/mb51/mb59 关于价格和金额的显示&#xff0c;需要权限控制&#xff0c;当权限对象F_BKPF_BUK,检查对应【公司代码】 和 ACTVT有03’的权限&#xff0c;如果没有03的权限&#xff0c;对应行的价格和金额显示为空 关于价格和金额的显示&#xff0c;需要权限控制&a…

媲美Sora,免费使用!带物理模拟的,文生视频模型

6月13日&#xff0c;知名3D建模平台Luma AI发布最新文生视频模型Dream Machine&#xff0c;向所有用户免费开放使用。 Dream Machine除了支持文本之外&#xff0c;还可使用图片作为引导来生成视频&#xff0c;其生成的视频质量、动作一致性、色彩、光影、饱和度、运镜等方面&a…