当前位置: 首页 > news >正文

多源最短路径算法 -- 弗洛伊德(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算法可能更加合适。

相关文章:

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

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

同三维T80005EH4 H.265 4路高清HDMI编码器

同三维T80005EH4 H.265 4路高清HDMI编码器 4路HDMI输入2路3.5音频输入&#xff0c;第1路和第2路HDMI可支持4K30&#xff0c;其它支持高清1080P60 产品简介&#xff1a; 同三维T80005EH4 4路HDMI高清H.265编码器采用最新高效H.265高清数字视频压缩技术&#xff0c;具备稳定…...

焦化行业排放平台简介

在当今社会&#xff0c;环保事业日益受到人们的关注。焦化行业作为重要的工业领域之一&#xff0c;其排放问题一直是环保工作的重点。为了有效控制焦化行业的排放&#xff0c;实施焦化行业排放平台成为了必不可少的措施。朗观视觉小编将详细探讨焦化行业排放平台的实施范围&…...

『原型资源』Axure自带图标库不够用,第三方经典图标库来袭

​今天小编为大家带来第三方经典图标库&#xff0c;己确认内容可用现推荐给大家。直接上手就可不用自己画哈~ 获取原型文档请与班主任联系&#xff01; 先睹为快&#xff0c;合适再拿走不谢&#xff1a; 图标太多&#xff0c;截取部分给大家参考o(*&#xffe3;︶&#xffe3;*…...

修改版的VectorDBBench更好用

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

六西格玛培训都培训哪些内容 ?

天行健六西格玛培训的内容通常涵盖多个方面&#xff0c;旨在帮助学员全面理解和应用六西格玛管理方法。以下是详细的培训内容概述&#xff1a; 一、六西格玛基础知识 引入六西格玛的概念、原理和历史&#xff0c;包括DMAIC&#xff08;定义、测量、分析、改进、控制&#xff0…...

K8S环境部署Prometheus

K8S环境部署Prometheus 记录在K8S 1.18版本环境下部署Prometheus 0.5版本。 1. 下载kube-prometheus仓库 git clone https://github.com/coreos/kube-prometheus.git cd kube-prometheus笔者安装的K8S版本是1.18 &#xff0c;prometheus选择配套的分支release-0.5&#xff1…...

在linux系统上挂载新硬盘

服务器的硬盘空间不够了&#xff0c;自己重新安装了一个硬盘&#xff0c;需要挂载&#xff0c;因为只是用来存放数据&#xff0c;所以不需要分区&#xff0c;直接挂载就可以 #查看当前所有硬盘 sudo fdisk -l #用于显示文件系统的磁盘空间使用情况 df -h发现一个/dev/nvme0n1 …...

1004.最大连续1的个数

给定一个二进制数组 nums 和一个整数 k&#xff0c;如果可以翻转最多 k 个 0 &#xff0c;则返回 数组中连续 1 的最大个数 。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,1,0,0,0,1,1,1,1,0], K 2 输出&#xff1a;6 解释&#xff1a;[1,1,1,0,0,1,1,1,1,1,1] 粗体数字…...

【机器学习300问】116、什么是序列模型?序列模型能干什么?

一、序列模型是什么&#xff1f; 序列模型是机器学习领域中专门设计来处理具有时间顺序或序列结构数据的模型。这类模型能够理解和学习数据中的顺序依赖关系&#xff0c;因此非常适合诸如自然语言处理、语音识别、音乐生成、时间序列预测等任务。 看了上面的定义&#xff0c;似…...

kafka 快速上手

下载 Apache Kafka 演示window 安装 编写启动脚本,脚本的路径根据自己实际的来 启动说明 先启动zookeeper后启动kafka,关闭是先关kafka,然后关闭zookeeper 巧记&#xff1a; 铲屎官&#xff08;zookeeper&#xff09;总是第一个到&#xff0c;最后一个走 启动zookeeper call bi…...

Python记忆组合透明度语言模型

&#x1f3af;要点 &#x1f3af;浏览器语言推理识别神经网络 | &#x1f3af;不同语言秽语训练识别数据集 | &#x1f3af;交互式语言处理解释 Transformer 语言模型 | &#x1f3af;可视化Transformer 语言模型 | &#x1f3af;语言模型生成优质歌词 | &#x1f3af;模型不确…...

如何保证数据库和缓存的一致性

背景&#xff1a;为了提高查询效率&#xff0c;一般会用redis作为缓存。客户端查询数据时&#xff0c;如果能直接命中缓存&#xff0c;就不用再去查数据库&#xff0c;从而减轻数据库的压力&#xff0c;而且redis是基于内存的数据库&#xff0c;读取速度比数据库要快很多。 更新…...

Java基础 - 多线程

多线程 创建新线程 实例化一个Thread实例&#xff0c;然后调用它的start()方法 Thread t new Thread(); t.start(); // 启动新线程从Thread派生一个自定义类&#xff0c;然后覆写run()方法&#xff1a; public class Main {public static void main(String[] args) {Threa…...

云顶之弈-测试报告

一. 项目背景 个人博客系统采用前后端分离的方法来实现&#xff0c;同时使用了数据库来存储相关的数据&#xff0c;同时将其部署到云服务器上。前端主要有四个页面构成&#xff1a;登录页、列表页、详情页以及编辑页&#xff0c;以上模拟实现了最简单的个人博客系统。其结合后…...

TCP/IP协议分析实验:通过一次下载任务抓包分析

TCP/IP协议分析 一、实验简介 本实验主要讲解TCP/IP协议的应用&#xff0c;通过一次下载任务&#xff0c;抓取TCP/IP数据报文&#xff0c;对TCP连接和断开的过程进行分析&#xff0c;查看TCP“三次握手”和“四次挥手”的数据报文&#xff0c;并对其进行简单的分析。 二、实…...

Python项目开发实战:企业QQ小程序(案例教程)

一、引言 在当今数字化快速发展的时代,企业对于线上服务的需求日益增长。企业QQ小程序作为一种轻量级的应用形态,因其无需下载安装、即开即用、占用内存少等优势,受到了越来越多企业的青睐。本文将以Python语言为基础,探讨如何开发一款企业QQ小程序,以满足企业的实际需求。…...

list模拟与实现(附源码)

文章目录 声明list的简单介绍list的简单使用list中sort效率测试list的简单模拟封装迭代器insert模拟erase模拟头插、尾插、头删、尾删模拟自定义类型迭代器遍历const迭代器clear和析构函数拷贝构造&#xff08;传统写法&#xff09;拷贝构造&#xff08;现代写法&#xff09; 源…...

Java应用中文件上传安全性分析与安全实践

✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; 目录 引言 一. 文件上传的风险 二. 使用合适的框架和库 1. Spr…...

noVNC 小记

1. 怎么查看Ubuntu版本...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

TJCTF 2025

还以为是天津的。这个比较容易&#xff0c;虽然绕了点弯&#xff0c;可还是把CP AK了&#xff0c;不过我会的别人也会&#xff0c;还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...