floyd算法详解

算法是一种用于求解所有顶点对之间的最短路径问题的算法,特别适用于稠密图。下面是一个使用C++实现的
算法示例:
#include <iostream>
#include <climits> // For INT_MAXusing namespace std;const int V = 4; // 图的顶点数// 定义一个函数来实现Floyd算法
void floyd(int graph[V][V]) {int dist[V][V];int i, j, k;// 初始化距离矩阵for (i = 0; i < V; i++)for (j = 0; j < V; j++)dist[i][j] = graph[i][j];// 运行Floyd算法for (k = 0; k < V; k++) {// 检查顶点k是否在i到j的路径上for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {if (dist[i][k] + dist[k][j] < dist[i][j])dist[i][j] = dist[i][k] + dist[k][j];}}}// 打印最短路径矩阵cout << "最短路径矩阵:\n";for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {if (dist[i][j] == INT_MAX)cout << "INF ";elsecout << dist[i][j] << " ";}cout << endl;}
}// 主函数
int main() {int graph[V][V] = { {0, 5, INT_MAX, 10},{INT_MAX, 0, 3, INT_MAX},{INT_MAX, INT_MAX, 0, 1},{INT_MAX, INT_MAX, INT_MAX, 0} };floyd(graph);return 0;
}
在这个示例中:
定义了图的顶点数。是一个二维数组,表示顶点之间的边权重,其中表示两个顶点之间没有直接的边。_
函数实现了算法,计算所有顶点对之间的最短路径,并打印结果。
你可以根据实际需要修改 和 的值,以适应不同的图结构。
但是注意:
算法的时间复杂度是

,可以处理负数边权的问题,所以时间要求一定要看清楚哦!
相关文章:
floyd算法详解
算法是一种用于求解所有顶点对之间的最短路径问题的算法,特别适用于稠密图。下面是一个使用C实现的算法示例: #include <iostream> #include <climits> // For INT_MAXusing namespace std;const int V 4; // 图的顶点数// 定义一个函数来…...
Web前端性能优化的方向
减少dom渲染复杂列表优化缓存优化首页背景图片加载慢,可以放在服务器上,读取绝对路径900k的图片大小有些大,可以对图片进行压缩,tinypng网站压缩、熊猫压缩、bing域名下的图片url后面带参数w、h、qlt剪裁下拉框数据较多进行懒加载…...
【面试题】设计模式-责任链模式
设计模式-责任链模式 前言责任链简历案例代码小结 前言 我们知道,设计模式是面试时经常被问到的问题之一,这是因为设计模式能够体现出代码设计的美感,且在很多框架的底层也都会使用到各种设计模式,所以对设计模式的考察ÿ…...
JavaEE 第8节 单例模式详解
目录 概念 饿汉模式 懒汉模式 懒汉模式在多线程环境下的优化 1.线程安全问题 2.效率问题 3.指令重排序导致的问题 1)为什么要进行指令重排序? 2)指令重排序在上述代码为什么会构成问题? 导读: 单例模式是一种…...
OpenAI 发布 GPT-4o 模型安全评估报告:风险等级为“中等”|TodayAI
OpenAI 近日发布了最新的 GPT-4o 系统卡,这是一份研究文件,详细介绍了公司在推出其最新 AI 模型之前所进行的安全措施和风险评估。根据该评估报告,GPT-4o 的总体风险等级被评定为 “中等” 。 GPT-4o 于今年 5 月首次公开发布。在其发布之前…...
学习前端面试知识
2024-8-9 打卡第十天 学习视频链接 js延迟加载 延迟加载:等页面加载完成后再进行加载提高页面加载速度defer属性,同步加载,让脚本与文档同步解析,顺序执行,当文档解析完成再执行defer,执行完再执行脚本&…...
Leetcode JAVA刷刷站(9)回文数
一、题目概述 二、思路方向 在Java中,判断一个整数是否为回文数,可以通过将该整数转换为字符串,然后比较字符串与其反转后的字符串是否相同来实现。但这种方法在整数非常大时可能不太高效,因为它依赖于字符串操作。一个更高效的方…...
数据结构算法
⩕ 单调栈 1、概念 对于一个栈,维持其单调性,有两种情况,单调递增栈:由栈底到栈顶单调递增 单调递减栈:由栈底到栈顶单调递减 2、核心模板( 单调递增栈 ) stack<int> stk; void …...
WordPress个性化站点
这个信息爆炸的时代,拥有一个能够迅速传达信息、展示个性、并能够与世界互动的在线平台,已成为企业和个人的基本需求。WordPress以其无与伦比的易用性和强大的扩展性,成为了构建此类平台的首选工具。而LNMP是由Linux、Nginx、MySQL和PHP组成的…...
GESP C++ 2024年03月一级真题卷
一、单选题(每题 2 分,共 30 分) 第 1 题 C表达式 (3 - 2) * 3 5 的值是( )。 A. -13 B. 8 C. 2 D. 0 答案:B 解析:略 第 2 题 C 语句 cout << "5%2" << 5 % 2 执行后的输出是…...
Linux驱动开发基础(Hello驱动)
所学内容来自百问网 目录 1. 文件在内核中的表示 2. 打开字符设备节点时,内核中也有对应的struct file 3. 编写驱动程序步骤 4. 相关知识点 4.1 涉及函数解析 4.2 module_init/module_exit的实现 4.3 register_chrdev的内部实现 4.4 class_destroy/device_…...
centos7安装 ES集群 elasticsearch
这里写自定义目录标题 编写启动脚本 elasticsearch.sh启动可能报错:elasticsearch 7.10启动报错 bootstrap checks failed解决方法问题原因:注意 退出xshell,重新登录: 上面两个配置项改完后,ES启动用户(es 或root) **…...
互联网应用主流框架整合【Redis数据结构及常用命令】
在大部分情况下我们使用Redis只是执行一些简单的命令操作,通常无需区分是否是在一个连接池里的同一个链接去执行,如果需要执行多条命令,需要保证命令在同一个链接里完成,则采用SessionCallback接口操作即可 Redis数据结构-字符串…...
GORM 自动迁移与命名策略
在现代软件开发中,数据库结构的维护和迁移是常见的挑战之一。GORM,作为 Go 语言中强大的 ORM 库,提供了自动迁移功能,帮助开发者轻松地管理数据库表结构的变更。此外,GORM 还允许开发者通过命名策略(Naming…...
python社会科学问题研究的计算实验
实验十五:社会科学问题研究的计算实践 1.实验目标及要求 (1)掌握网络视角 (2)掌握社会网络基础内容 (3)掌握友谊悖论 2.实验主要内容 随机生成一次符合社会网络特征的网络,通过计…...
Element Plus 发布 2.8.0
功能特性 组件更新 [color-picker] alpha-slider a11y (#14245 by tolking)添加 mention 组件 (#17586 by Fuphoenixes)[tree-v2] 添加 scrollTo 方法 (#14050 by kaine0923)[drawer] 添加 append-to 属性 (#17761 by tolking)[table] tree children 添加严格检查 (#13519 by t…...
解释区块链技术的应用场景和优势-水文
区块链技术是一种去中心化的分布式账本技术,其应用场景和优势如下: 金融领域:区块链可以用于加密货币交易,提供安全的、去中心化的支付系统。它也可以用于股票、债券和其他金融交易的记录和结算,提高交易的透明度和效率…...
等保测评基础知识(一)
1、时间类: 网络安全法: 2017年6月1日等保2.0实施时间: 2019年12月1日密码法: 2020年1月1日个人信息保护法: 2021年11月1日,数据安全法实施时间: 2021年9月1日关键信息基础…...
股指期货套期保值中的展期管理有哪些?
在复杂的金融市场环境中,展期作为一种重要的风险管理工具,被广泛应用于期货交易中,特别是当投资者需要对长期资产进行套期保值时。展期的核心思想在于,通过连续替换高流动性的近月期货合约来替代流动性较差的远月合约,…...
如何通过参考文献找到原文
当只有参考文献想要获取原文时,通常会用到以下方法: 举例参考文献1. 杨忠华,周勃,宁宝宽,等.面向新能源产业的专业研究生研创能力培养实践探索——基于“政产学研用”融合驱动[J].高教学刊,2024,10(23):19-22.DOI:10.19980/j.CN23-1593/G4.2024.23.004…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
