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

最短路问题--Floyd

news 来源：原创 2025/9/12 10:16:28

Floyd算法

一、介绍
二、补充知识：邻接矩阵
三、原理
四、实现

提示：以下是本篇文章正文内容，下面案例可供参考

一、介绍

Floyd算法是一种用来计算图中所有点之间最短距离的算法。它的核心思想是：通过逐步尝试每个点作为中间点，看看能不能让其他两点之间的距离变得更短。

二、补充知识：邻接矩阵

邻接矩阵是一种用来表示图的结构的工具，它用一个二维数组来记录图中各个顶点之间的关系。简单来说，就是用一个表格来描述图中哪些点之间有边，以及边的权重。

邻接矩阵的定义

假设有一个图，包含 n 个顶点，编号为 1 到 n。邻接矩阵是一个 n×n 的二维数组 adj，其中：
adj[i][j] 表示顶点 i 和顶点 j 之间的关系。
如果顶点 i 和 j 之间有边，那么 adj[i][j] 的值是边的权重（如果是无权图，则标记为 1）。
如果顶点 i 和 j 之间没有边，那么 adj[i][j] 的值通常设为 0 或无穷大（取决于具体需求，一般inf）

2.说简单一点

行对应元素到列元素的距离，就是存在矩阵的值
对角线为0，因为自己到自己为0

三、原理

1.首先创建一个邻接矩阵，全部设为0
2.初始化邻接矩阵，即此时不使用中转节点，就是点到点的直接距离，倘若点到点走不通，那就设为inf即可，记住：邻接矩阵的对角线一点都是0
3.遍历所有节点作为中转节点，这个点所在的行列无需变动，原理如下：

倘若1为中间节点，则1->2和1->1->2没有区别，自己到自己距离为0，同理3->1,和3->1->1也是一样的

4.对于除上述所说的自己的行列除外，对角线也除外，剩下的元素开始迭代更新
5.如果经过了中转节点的路劲之和小于上一步的，就更新矩阵，知道结束

上述内容若觉得云里雾里：推荐这个视频——>B站up主sunny光合

四、实现

以下代码，包括回溯路径，使用字典转邻接矩阵

graph={'A':{'B':1,'C':4},'B':{'A':1,'C':2,'D':5},'C':{'A':4,'B':2,'D':1},'D':{'B':5,'C':1}
}def floyd(graph):# 获取顶点列表vertices = list(graph.keys())n = len(vertices)# 初始化距离矩阵和路径矩阵dist = [[float('inf')] * n for _ in range(n)]next = [[None] * n for _ in range(n)]# 填充邻接矩阵和路径矩阵for i in range(n):for j in range(n):if i == j:dist[i][j] = 0elif vertices[j] in graph[vertices[i]]:dist[i][j] = graph[vertices[i]][vertices[j]]next[i][j] = j  # 记录路径，从i到j的下一跳是j# Floyd算法核心for k in range(n):  # 中间点for i in range(n):  # 起点for j in range(n):  # 终点if dist[i][k] + dist[k][j] < dist[i][j]:dist[i][j] = dist[i][k] + dist[k][j]next[i][j] = next[i][k]  # 更新路径# 打印最短路径长度矩阵print("最短路径长度矩阵：")for row in dist:print(row)# 回溯路径def reconstruct_path(start, end):if dist[start][end] == float('inf'):return None  # 无路径path = [start]while start != end:start = next[start][end]path.append(start)return path# 打印路径print("\n路径信息：")for i in range(n):for j in range(n):if i != j:path = reconstruct_path(i, j)if path:print(f"{vertices[i]} -> {vertices[j]}: {list(map(lambda x: vertices[x], path))}")else:print(f"{vertices[i]} -> {vertices[j]}: 无路径")# 调用算法
floyd(graph)

输出结果

最短路径长度矩阵：
[0, 1, 3, 4]
[1, 0, 2, 3]
[3, 2, 0, 1]
[4, 3, 1, 0]路径信息：
A -> B: ['A', 'B']
A -> C: ['A', 'B', 'C']
A -> D: ['A', 'B', 'C', 'D']
B -> A: ['B', 'A']
B -> C: ['B', 'C']
B -> D: ['B', 'C', 'D']
C -> A: ['C', 'B', 'A']
C -> B: ['C', 'B']
C -> D: ['C', 'D']
D -> A: ['D', 'C', 'B', 'A']
D -> B: ['D', 'C', 'B']
D -> C: ['D', 'C']

声明：
本文为本人的学习笔记，旨在记录和分享个人在学习过程中的心得体会和原创代码。由于本人刚入门，对相关知识的理解可能还存在不足之处，文章中难免会有错误或不准确的地方。在此，我诚挚地欢迎各位读者在阅读过程中，如果发现任何问题或有其他建议，随时在评论区或通过其他方式与我交流。我将虚心听取大家的意见，及时修正和改进文章内容，以便更好地学习和成长。感谢大家的关注和支持！

最短路问题--Floyd

Floyd算法一、介绍二、补充知识：邻接矩阵三、原理四、实现提示：以下是本篇文章正文内容，下面案例可供参考一、介绍 Floyd算法是一种用来计算图中所有点之间最短距离的算法。它的核心思想是：通过逐步尝试每个点作为中间点&…...

编程日记 2025/9/12 10:16:28

深入理解Java网络编程：从基础到高级应用

一、网络编程概述 1.什么是网络编程？ 网络编程是指利用计算机网络实现程序之间通信的一种编程方式。在网络编程中，程序需要通过网络协议（如 TCP/IP）来进行通信，以实现不同计算机之间的数据传输和共享。 2.在网络编程…...

编程日记 2025/9/12 10:14:16

浅谈deepseek环境搭建

在探索人工智能的浩瀚宇宙中，DeepSeek如同一颗璀璨的星辰，以其独特的魅力引领着我们在逻辑推理与数据分析的海洋中遨游。想要在这片未知的领域里扬帆起航，首先必须精心搭建起我们的“星际飞船”——DeepSeek环境。无论你是渴望在本地实例上运…...

编程日记 2025/9/12 10:14:19

AI绘画软件Stable Diffusion详解教程（2）：Windows系统本地化部署操作方法（专业版）

一、事前准备 1、一台配置不错的电脑，英伟达显卡，20系列起步，建议显存6G起步，安装win10或以上版本，我的显卡是40系列，16G显存，所以跑大部分的模型都比较快； 2、科学上网&#xff0…...

编程日记 2025/9/12 10:09:10

kali liux的下载

Kali Linux | Penetration Testing and Ethical Hacking Linux Distributionhttps://www.kali.org/ VMware虚拟机https://pan.quark.cn/s/aa869ffbf184 【补充一个今天学到的知识昂和内容无关:（遥感）指非接触的远距离探测技术，使用传感器探…...

编程日记 2025/9/12 10:10:07

DeepSeek 助力 Vue3 开发：打造丝滑的悬浮按钮（Floating Action Button）

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏关注哦 💕 目录 Deep…...

编程日记 2025/9/12 10:16:12

ES from size聚合查询10000聚合查询，是每个分片先聚合，再统计。还是所有节点查询1万条后，再聚合

在 Elasticsearch 中，聚合查询的执行过程是分布式的，Elasticsearch 会先在每个分片（shard）上执行本地聚合，然后再在协调节点（coordinating node）上对所有分片的聚合结果进行全局汇总。具体过…...

编程日记 2025/9/12 10:16:14

fluent-ffmpeg 依赖详解

fluent-ffmpeg 是一个用于在 Node.js 环境中与 FFmpeg 进行交互的强大库，它提供了流畅的 API 来执行各种音视频处理任务，如转码、剪辑、合并等。一、安装 npm install fluent-ffmpeg二、基本使用要使用 fluent-ffmpeg，首先需要确保系统中…...

编程日记 2025/9/12 10:14:16

SLAM文献之-DROID-SLAM: Deep Visual SLAM for Monocular, Stereo, and RGB-D Cameras

DROID-SLAM 是一种结合深度学习与传统视觉SLAM技术的先进算法，其核心目标是通过端到端可训练的深度神经网络来实现高精度的相机位姿估计和稠密三维重建。与传统SLAM方法不同，DROID-SLAM采用深度学习网络来估计深度信息，提供更高的精度与鲁棒性…...

编程日记 2025/9/12 10:16:13

一、旋转编码器模块分析与使用

一、旋转编码器说明该模块配合定时器的encoder使用时，可通过旋转来进行调整记录编码的数值。（通过旋转编码器的数值与字母建立对应关系，即可进行打字编码） 引脚说明： vcc，gnd，供电使用 sw&am…...

编程日记 2025/9/12 1:52:14

【踩坑日志】解决CU118环境下RuntimeError: NCCL error: invalid usage

本博客主要记录了CU118环境下，出现报错信息为RuntimeError: NCCL error: invalid usage的解决方案。我的环境信息如下： cuda版本：11.7torch版本：torch-2.5.1-cu118 定位到核心报错信息为： NCCL WARN NCCL cannot be …...

编程日记 2025/9/11 21:02:12

FREERTOS的三种调度方式

一、调度器的调度方式调度器的调度方式解释针对的对象抢占式调度1.高优先级的抢占低优先级的任务 2.高优先级的任务不停止，低优先级的任务不能执行 3.被强占的任务会进入就绪态优先级不同的任务时间片调度1.同等优先级任务轮流享用CPU时间 2.没有用完的时间片&…...

编程日记 2025/9/7 14:11:33

338.比特位计数＜动态规划＞

338. 比特位计数 - 力扣（LeetCode） class Solution { public:vector<int> countBits(int n) {//将所有数初始化为0vector<int>dp(n1,0);for(int i 0; i<n;i){if(i % 2 0){dp[i] dp[i/2];}else{dp[i] dp[i/2]1;}}return dp;} };...

编程日记 2025/9/7 20:21:43

释放你的IDE潜能：Code::Blocks 插件创意开发深度指南

释放你的IDE潜能：Code::Blocks 插件创意开发深度指南在软件开发的浩瀚世界中，集成开发环境 (IDE) 扮演着至关重要的角色。一款优秀的 IDE 不仅能提升开发效率，更能激发开发者的创造力。Code::Blocks，作为一款开源、跨平台的 C, C++ 和 Fortran IDE，以其轻量级、高度可定…...

编程日记 2025/9/12 7:01:10

行星际激波与高能粒子的相互作用机制及其天体物理意义

第一章行星际激波的物理本质与形成机制 1.1 激波的普遍定义与分类激波（Shock Wave）是介质中传播的压缩性不连续面，其本质是介质参数（如密度、速度、压力）的突变。在天体物理中，根据激波传播方向与磁场…...

编程日记 2025/9/10 1:10:03

C# 牵手DeepSeek：打造本地AI超能力

一、引言在人工智能飞速发展的当下，大语言模型如 DeepSeek 正掀起新一轮的技术变革浪潮，为自然语言处理领域带来了诸多创新应用。随着数据隐私和安全意识的提升，以及对模型部署灵活性的追求，本地部署 DeepSeek 成为众多开发者和…...

编程日记 2025/9/6 19:05:22

不同版本的BLE和WiFi有什么区别？

一、蓝牙技术对比：从 Bluetooth 4.0 到 5.3 的演进与室内定位应用蓝牙技术自推出以来，经历了多次重大升级，每一代都在传输速率、功耗、覆盖范围和功能上有所改进。本文将从 Bluetooth 4.0 到 5.3，逐一对比各版本的特点&#xff0…...

编程日记 2025/9/11 3:44:39

LVS+Keepalived高可用高性能负载实战

高可用集群（ High Availability Cluster, HA 集群），其中高可用的含义是最大限度地可以使用。从集群的名字上可以看出，此类集群实现的功能是保障用户的应用程序持久、不间断地提供服务。当应用程序出现故障或者系统硬件、网络出现…...

编程日记 2025/9/11 4:08:28

网络安全-使用DeepSeek来获取sqlmap的攻击payload

文章目录概述DeepSeek使用创建示例数据库创建API测试sqlmap部分日志参考概述今天来使用DeepSeek做安全测试，看看在有思路的情况下实现的快不快。 DeepSeek使用我有一个思路，想要测试sqlmap工具如何dump数据库的： 连接mysql数据库&#…...

编程日记 2025/9/2 16:21:23

【MongoDB】在Windows11下安装与使用

官网下载链接：Download MongoDB Community Server 官方参考文档：https://www.mongodb.com/zh-cn/docs/manual/tutorial/install-mongodb-on-windows/#std-label-install-mdb-community-windows 选择custom类型，其他默认注意，此选…...

编程日记 2025/9/11 10:14:59

vscode输入！＋tab没反应？？

！＋tab直接生成html框架第一步 ctrlshipp 选择更改语言模式 change language mode， 选择HTML 然后试一下行不行，如果还不行看第二步第二步检查一下输入的！是不是英文输入法输入的，一定要是英文输入&…...

编程日记 2025/9/5 22:48:03

【Cadence射频仿真学习笔记】2.4GHz低噪放LNA仿真设计

课程分为3个部分， 一、LNA结构与噪声优化方法噪声优化的方法是：限定功耗的噪声和功率同时匹配噪声匹配和功率匹配一般不会同时达到， 对于PCSNIM结构的噪声分析，我们只需要了解与哪些参数有关优化思路是：1.信号源阻抗…...

编程日记 2025/9/11 7:04:24

初阶MySQL（两万字全面解析)

文章目录 1.初识MySQL1.1数据库1.2查看数据库1.3创建数据库1.4字符集编码和排序规则1.5修改数据库1.6删除数据库 2.MySQL常用数据类型和表的操作2.(一)常用数据类型1.数值类2.字符串类型3.二进制类型4.日期类型 2.(二)表的操作1查看指定库中所有表2.创建表 3.查看表结构和查看表…...

编程日记 2025/9/10 13:45:48

Python每日一练：学习指南进行汇总

Python，一种“优雅”、“明确”、“简单”的编程语言，凭借其低学习曲线、强大的开源生态系统、卓越的平台可移植性以及面向对象和函数式编程的支持，成为了众多开发者首选。 01 Python 应用领域和就业形势分析 Python，一种“优雅…...

编程日记 2025/9/9 20:24:27

Spring-AI搭建企业专属知识库一

环境介绍：Spring3.3.2 JDK 21 POM文件 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation&…...

编程日记 2025/9/9 21:17:52

Python的那些事第三十六篇：基于 Vega 和 Vega-Lite 的数据可视化解决方案，Altair 声明式可视化库

Altair 声明式可视化库：基于 Vega 和 Vega-Lite 的数据可视化解决方案摘要在数据科学和分析领域，有效的数据可视化是理解数据、发现模式和传达见解的关键。Python 作为数据科学的主要编程语言之一，提供了多种数据可视化库。其中，Altair 是一个基于 Vega 和 Vega-Lite 的…...

编程日记 2025/9/7 7:40:39

虚拟化园区网络部署指南

《虚拟化园区网络部署指南》属于博主的“园区网”专栏，若想成为HCIE，对于园区网相关的知识需要非常了解，更多关于园区网的内容博主会更新在“园区网”专栏里，请持续关注！ 一.前言华为CloudCampus解决方案基于智简网络…...

编程日记 2025/9/7 21:42:06

系统调用有哪些函数

系统调用是操作系统提供给用户程序的一组“特殊”的函数接口，允许用户程序请求操作系统执行某些低级服务。这些服务通常涉及对硬件的直接操作或访问受保护的内核资源。以下是一些常见的系统调用函数，主要基于Unix/Linux环境： 一、文件与设备…...

编程日记 2025/9/11 19:44:58

Go红队开发—编解码工具

文章目录开启一个项目编解码工具开发Dongle包Base64编解码摩斯密码URL加解密AES加解密 MD5碰撞工具开发开启一个项目这作为补充内容，可忽略直接看下面的编解码： 一开始用就按照下面的步骤即可 1.创建一个文件夹，你自己定义名字(建议只用…...

编程日记 2025/9/7 5:44:57

PyInstaller 打包python 程序成可执行文件

pyinstaller --onefile --name my_project --add-data "config/config.json:config" main.py 要将整个 Python 项目打包成一个可执行文件，可以使用 PyInstaller 来完成这个任务。以下是如何将整个项目打包成可执行文件的步骤： 1. 安装 PyIns…...

编程日记 2025/9/12 0:29:29

引用库如下： 读取shapefile代码如下： namespace IfoxDemo {public class Class1{[CommandMethod("xx")]public static void nts二次学习(){Document doc Application.DocumentManager.MdiActiveDocument;var ed doc.Editor;string shpPath …...

编程日记 2025/9/8 16:42:25

Python爬虫

python凭借其简洁的语法和强大的库支持，成为编写爬虫程序的首选语言之一。今天，我将通过一个简单的示例，带你入门Python爬虫，并展示如何爬取网页内容并保存到文本文件中。一、爬虫的基本概念爬虫（Web Crawler&#…...

编程日记 2025/9/8 13:46:40

C++蓝桥杯基础篇（六）

片头嗨~小伙伴们，大家好！今天我们来一起学习蓝桥杯基础篇（六），练习相关的数组习题，准备好了吗？咱们开始咯！ 第1题数组的左方区域这道题，实质上是找规律，…...

编程日记 2025/9/11 16:06:15

rust学习～tokio的io

await Suspend execution until the result of a Future is ready. 暂停执行，直到一个 Future 的结果就绪。 .awaiting a future will suspend the current function’s execution until the executor has run the future to completion. 对一个 Future 使用 .awa…...

编程日记 2025/9/8 22:22:15

JVM--虚拟机

JVM,即虚拟机，可以简单理解为将字节码文件翻译成机器码的机器。 .class文件-->机器码文件 JVM整体组成部分 1.类加载器负责从磁盘中加载字节码文件到JVM中 2.运行时数据区按照不同的数据分区进行存储(方法区，堆，栈，本地方…...

编程日记 2025/9/5 16:48:29

【Unity】把Texture的黑色背景改成透明背景

1. 在Project窗口中选择目标Texture 2. 在Inspector窗口中进行如下设置： Texture Type: Sprite (2D and UI)Alpha Source: Input Texture Alpha (如果原图有Alpha通道) 或 From Gray Scale (如果要用灰度值作为透明度)Alpha Is Transparency: ✓ (勾选) 3. 其他建…...

编程日记 2025/9/8 19:28:57

计算机毕业设计SpringBoot+Vue.js华强北商城二手手机管理系统 (源码+文档+PPT+讲解)

温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 作者简介：Java领…...

编程日记 2025/9/11 18:46:12

利用 Python 爬虫进行跨境电商数据采集

1 引言2 代理IP的优势3 获取代理IP账号4 爬取实战案例---（某电商网站爬取）4.1 网站分析4.2 编写代码4.3 优化代码 5 总结 1 引言在数字化时代，数据作为核心资源蕴含重要价值，网络爬虫成为企业洞察市场趋势、学术研究探索未知领域…...

编程日记 2025/9/9 17:54:47

Android中使用Robolectric测试点击事件(不需要手机)

文章目录一、前言二、简单示例三、参考文档一、前言 Robolectric 是一个由 Google 维护的开源 Android 测试框架，它允许你以 Android 运行时环境运行单元测试。 Robolectric 提供了一个模拟 Android 运行时环境，允许你测试你的代码是否正确地使用 And…...

编程日记 2025/9/11 3:49:43

如何把网络ip改为动态：全面指南

在数字化时代，网络IP地址作为设备在网络中的唯一标识，扮演着至关重要的角色。随着网络环境的不断变化，静态IP地址的局限性逐渐显现，而动态IP地址则因其灵活性和安全性受到越来越多用户的青睐。那么，如何把网络IP改为动…...

编程日记 2025/9/7 4:12:16

文件描述符与重定向

1. open系统调用在 Linux 中, open() 系统调用用于打开一个文件或设备，并返回一个文件描述符，通过该描述符可以进行文件读写操作。open() 可以用于创建新文件或打开已存在的文件，具体行为取决于传递给它的参数。需要包含的头文件&#xf…...

编程日记 2025/9/11 22:46:03

自然语言处理NLP入门 -- 第六节命名实体识别

1 什么是命名实体识别？ 在日常生活中，我们经常会遇到这样的情景：希望从一大段文本中，快速找出所有的人名、地名、组织机构名称、日期、时间等关键信息。举个例子，如果你在阅读一篇关于历史事件的新闻报道时&#xff0…...

编程日记 2025/9/10 15:13:21

Windows PicPick Professional-v7.3.2-中文版

Windows PicPick Professional-中文版链接：https://pan.xunlei.com/s/VOKGwGVGWUDl7L8cW4D1A1W4A1?pwdw5qz# - 更新了中文翻译，默认取消检测升级，删除多国语言...

编程日记 2025/8/16 10:45:09

Hue UI展示中文

个人博客地址：Hue UI展示中文 | 一张假钞的真实世界如果使用开发分支代码如master分支）编译安装，需要自己编译语言文件。例如Hue安装目录为“/opt/hue”，则安装后执行以下命令： $ cd /opt/hue $ make locales 如果…...

编程日记 2025/9/8 9:36:11

【Unity】AI Navigation自动寻路（导航）功能

1.简介以及安装AI Navigation 1.1 简介 AI导航包包含高级组件，允许你在游戏中使用导航网格来整合导航和寻径。有了这个包，你可以在运行时和编辑时构建和使用导航网格，创建动态障碍，并使用链接来允许特定的动作（如跳跃…...

编程日记 2025/9/11 5:57:55

网络安全员证书

软考网络安全员证书：信息安全领域的黄金标准随着信息技术的飞速发展，网络安全问题日益凸显，网络安全员的需求也日益增加。软考网络安全员证书作为信息安全领域的黄金标准，对于网络安全从业者来说具有重要意义。本文将详细介绍…...

编程日记 2025/9/7 10:16:49

2.你有什么绝活儿？—Java能做什么？

1、Java的绝活儿：要问Java有什么绝活，我觉得它应该算是一位魔法师，会的绝活儿有很多，要说最能拿得出手的当属以下三个。 1.1 平台无关性：Java可以在任何地方施展魔法，无论是Windows、Linux还是Mac&#xf…...

编程日记 2025/9/11 2:29:09

使用 ASP.NET Core 创建和下载 zip 文件

对于最近的一个功能，我必须从用 ASP.NET Core 编写的内部网站下载一批文件。在下载文件之前对其进行压缩，结果证明这是一种轻松实现多文件下载的好方法。.NET 提供了所有需要的功能，在本文中，我将向您展示如何实现它。首先&#…...

编程日记 2025/9/8 1:12:43

数据结构之队列

一、队列的概念队列是一个有序列表，可以用数组或者是链表来实现的。遵循的是先入先出的原则，就是先存入队列的数据要先取出，后面存的需要后面取出。插入的一端称为队尾，删除的一端称为队头，队列里没有元素就称它为空…...

编程日记 2025/9/10 15:46:51

微信小程序读取写入NFC文本，以及NFC直接启动小程序指定页面

一、微信小程序读取NFC文本(yyy优译小程序实现)，网上有很多通过wx.getNFCAdapter方法来监听读取ＮＦＣ卡信息，但怎么处理读取的message文本比较难找，现用下面方法来实现，同时还解决几个问题，1、在回调方法中this.setData不更新信息，因为this的指向问题，2、在退出页面时，…...

编程日记 2025/9/10 20:08:29

Floyd算法

一、介绍

二、补充知识：邻接矩阵

三、原理

四、实现

相关文章：