当前位置: 首页 > 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版本...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...