数据结构与算法之Floyd弗洛伊德算法求最短路径
目录
前言
Floyd弗洛伊德算法
定义
步骤
一、初始化
二、添加中间点
三、迭代
四、得出结果
时间复杂度
代码实现
结束语
前言
今天是坚持写博客的第18天,希望可以继续坚持在写博客的路上走下去。我们今天来看看数据结构与算法当中的弗洛伊德算法。
Floyd弗洛伊德算法
定义
Floyd弗洛伊德算法是一种用于在加权图中找到所有顶点对之间的最短路径的算法。这个算法可以处理带有正权、负权甚至零权(但不存在负权环路)的图。
对于了解Floyd弗洛伊德算法,我们需要先了解几个前置概念:
- 加权图:图中的每条边都有一个与之关联的权值
- 最短路径:从一个顶点到另一个顶点的总权值最小的路径
- 负权环路:一个环路(即一条起点和终点相同的路径),其所有边的权值之和为负。如果存在负权环路,则最短路径问题可能没有解,因为可以通过无限次地遍历这个环路来不断减小路径的总权值。
步骤
假设我们有如下的图:

其中A到B的权值为2,A到C的权值为6,A到D的权值为5,B到C的权值为1,B到D的权值为4,C到D的权值为3。我们可以先得出他的邻接矩阵:

为什么对角线上的值都是零?因为对角线上的路径都是一个环路,图上没有自己指向自己的环路,因此都是0。
下面进入正题,如何使用弗洛伊德算法呢?
一、初始化
首先,为图中所有顶点对(i, j)之间设置一个距离矩阵D,其中D[i][j]表示从顶点i到顶点j的当前已知最短距离。如果两个顶点之间没有直接相连的边,则设置D[i][j]为一个很大的数(通常是一个无穷大的值,表示为∞)。如果两个顶点之间有直接相连的边,则设置D[i][j]为该边的权值。另外,设置一个中间矩阵P,用于记录最短路径的信息。
二、添加中间点
- 对于图中的每一个顶点k(作为中间点),遍历所有顶点对(i, j)(其中i和j是图中的顶点且i ≠ j,i ≠ k,j ≠ k)。
- 如果从i到k再到j的路径比已知的i到j的路径更短(即dist[i][k] + dist[k][j] < dist[i][j]),则更新dist[i][j]为dist[i][k] + dist[k][j]。
三、迭代
重复步骤二,对于图中的每一个顶点k都执行一次。由于图中总共有n个顶点,因此这个步骤需要执行n次迭代。
四、得出结果
在完成所有迭代后,dist矩阵将包含图中所有顶点对之间的最短路径长度。如果dist[i][j]的值仍然是无穷大,则表示从顶点i到顶点j没有路径。
时间复杂度
Floyd算法的时间复杂度为O(n^3),其中n是图中顶点的数量。这是因为算法需要进行n次迭代,每次迭代都需要检查所有n^2个顶点对。
代码实现
下面是大家期待的代码实现,今天我们用python实现
import numpy as np def floyd_warshall(graph): n = len(graph) # 复制邻接矩阵作为距离矩阵 dist = np.copy(graph) # 遍历所有顶点作为中间点 for k in range(n): # 遍历所有顶点对 (i, j) for i in range(n): for j in range(n): # 如果通过顶点 k 可以找到更短的路径 if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist # 示例图(邻接矩阵)
graph = np.array([ [0, 5, float('inf'), 10], [float('inf'), 0, 3, float('inf')], [float('inf'), float('inf'), 0, 1], [float('inf'), float('inf'), float('inf'), 0]
]) # 调用 Floyd-Warshall 算法
distances = floyd_warshall(graph) # 打印结果
print("Shortest distances between all pairs of vertices:")
print(distances)
结束语
以上就是今天对弗洛伊德算法求解最短路径的解释,希望对大家有所帮助,如果对您有帮助,希望您可以留下一个点赞、关注和收藏,这对我很重要,谢谢!
相关文章:
数据结构与算法之Floyd弗洛伊德算法求最短路径
目录 前言 Floyd弗洛伊德算法 定义 步骤 一、初始化 二、添加中间点 三、迭代 四、得出结果 时间复杂度 代码实现 结束语 前言 今天是坚持写博客的第18天,希望可以继续坚持在写博客的路上走下去。我们今天来看看数据结构与算法当中的弗洛伊德算法。 Flo…...
Ubuntu系统设置Redis与MySQL登录密码
Ubuntu系统设置Redis与MySQL登录密码 在Ubuntu 20.04系统中配置Redis和MySQL的密码,您需要分别对两个服务进行配置。以下是详细步骤: 配置Redis密码 打开Redis配置文件: Redis的配置文件通常位于/etc/redis/redis.conf。 sudo nano /etc/redis/redis.c…...
数据库连接池的概念和原理
目录 一、什么是数据库连接池 二、数据库连接池的工作原理 1.初始化阶段: 2.获取连接: 3.使用连接: 4.管理和优化: 三、数据库连接池的好处 一、什么是数据库连接池 数据库连接池(Database Connection Pooling&…...
国内常用的编程博客网址:技术资源与学习平台
一、国内常用的编程博客网址:技术资源与学习平台 大家初入编程,肯定会遇到各种各样的问题。我们除了找 AI 工具以外,我们还能怎么迅速解决问题呢? 大家可以通过谷歌,百度,必应,github…...
怎么给三极管基极或者MOS管栅极接下拉电阻
文章是瑞生网转载,PDF格式文章下载: 怎么给三极管基极或者MOS管栅极接下拉电阻.pdf: https://url83.ctfile.com/f/45573183-1247189078-52e27b?p7526 (访问密码: 7526)...
Java Web学习笔记5——基础标签和样式
<!DOCTYPE html> html有很多版本,那我们应该告诉用户和浏览器我们现在使用的是HMTL哪个版本。 声明为HTML5文档。 字符集: UTF-8:现在最常用的字符编码方式。 GB2312:简体中文 BIG5:繁体中文、港澳台等方式…...
01_深度学习基础知识
1. 感知机 感知机通常情况下指单层的人工神经网络,其结构与 MP 模型类似(按照生物神经元的结构和工作原理造出来的一个抽象和简化了模型,也称为神经网络的一个处理单元) 假设由一个 n 维的单层感知机,则: x 1 x_1 x1 至 x n x_n xn 为 n 维输入向量的各个分量w 1 j…...
60、最大公约数
最大公约数 题目描述 给定n对正整数ai,bi,请你求出每对数的最大公约数。 输入格式 第一行包含整数n。 接下来n行,每行包含一个整数对ai,bi。 输出格式 输出共n行,每行输出一个整数对的最大公约数。 数据范围 1 ≤ n ≤ 1 0 5 , 1≤n≤…...
设计模式在芯片验证中的应用——迭代器
一、迭代器设计模式 迭代器设计模式(iterator)是一种行为设计模式, 让你能在不暴露集合底层表现形式 (列表、 栈和树等数据结构) 的情况下遍历集合中所有的元素。 在验证环境中的checker会收集各个monitor上送过来的transactions࿰…...
imx6ull - 制作烧录SD卡
1、参考NXP官方的手册《i.MX_Linux_Users_Guide.pdf》的这一章节: 1、SD卡分区 提示:我们常用的SD卡一个扇区的大小是512字节。 先说一下i.MX6ULL使用SD卡启动时的分区情况,NXP官方给的镜像布局结构如下所示: 可以看到,…...
使用chatgpt api快速分析pdf
需求背景 搞材料的兄弟经常要分析pdf,然后看到国外有产品是专门调用chatpdf来分析pdf的,所以就来问我能不能帮他也做一个出来。正好我有chatgpt的api,所以就研究了一下这玩意怎么弄。 需求分析 由于chatgpt是按字符算钱的,所以…...
Vue:状态管理pinia
安装 npm install pinia在 main.js 中注册 // main.jsimport { createApp } from vue import { createPinia } from "pinia"; import App from ./app.vueconst app createApp(App) const pinia createPinia(); app.use(pinia).mount(#app)创建 store // stores/…...
【Android Studio】导入import android.support.v7.app.AppcompatActivity;时报错
一、问题描述 在进行安卓项目开发时使用import android.support.v7.app.AppcompatActivity;报错: 运行后会有乱码出现: 二、解决办法 将import android.support.v7.app.AppcompatActivity;改为import androidx.appcompat.app.AppCompatActivity;基本上…...
汽车区域控制器技术分析
汽车区域控制器的起源与发展 随着汽车技术的不断发展,汽车电子电气架构也在经历着深刻的变革。汽车区域控制器作为一种新兴的技术,正逐渐成为汽车电子电气架构的重要组成部分。 在早期,汽车电子电气架构主要采用分布式架构。这种架构下,各个电子控制单元(ECU)分别负责不…...
myEclipse新手使用教程
myEclipse新手使用教程 一、引言 myEclipse是一款流行的Java集成开发环境(IDE),它集成了众多的开发工具,为Java开发者提供了一个强大的开发平台。本文将详细介绍如何下载、安装和配置myEclipse,以及如何创建一个简单…...
【WPF编程宝典】第6讲:资源
研究了 WPF 资源系统使得在应用不同部分可以重用相同对象的原理,介绍了如何在代 码和标记中声明资源,如何提取系统资源,以及如何使用类库程序集在应用程序之间共享资源。 1.资源基础 1.1静态资源和动态资源 区别:静态资源只从资…...
容器化部署Pig微服务快速开发框架
系统说明 基于 Spring Cloud 、Spring Boot、 OAuth2 的 RBAC 企业快速开发平台, 同时支持微服务架构和单体架构 提供对 Spring Authorization Server 生产级实践,支持多种安全授权模式 提供对常见容器化方案支持 Kubernetes、Rancher2 、Kubesphere、E…...
Windows编程:图标资源、光标资源、字符串资源、加速键资源、WM_PAINT消息、绘图
承接前文: win32窗口编程windows 开发基础win32-注册窗口类、创建窗口win32-显示窗口、消息循环、消息队列win32-鼠标消息、键盘消息、计时器消息、菜单资源 本文目录 图标资源光标资源WM_SETCURSOR 消息 字符串资源加速键资源WM_PAINT 消息绘图绘图编程绘图基础基…...
【2024 短剧0元轻资产创业风口】做自己的老板,做新媒体的领路人
好省短剧邀请码2Urux1ZoQm(长按复制粘贴即可)大多数好省短剧推广活动都会通过官方渠道发布邀请码。您可以通过关注官方社交媒体账号、订阅电子邮件通知或参与官方网站上的活动,获得邀请码的机会。官方渠道通常会提前公布邀请码的获取方式和条件,您只需按照要求执行即可。好省…...
Docker安装Bitbucket
centos7版本 [rootlocalhost ~]# cat /etc/os-release NAME"CentOS Linux" VERSION"7 (Core)" ID"centos" ID_LIKE"rhel fedora" VERSION_ID"7" PRETTY_NAME"CentOS Linux 7 (Core)" ANSI_COLOR"0;31"…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
如何通过git命令查看项目连接的仓库地址?
要通过 Git 命令查看项目连接的仓库地址,您可以使用以下几种方法: 1. 查看所有远程仓库地址 使用 git remote -v 命令,它会显示项目中配置的所有远程仓库及其对应的 URL: git remote -v输出示例: origin https://…...
