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

floyd算法详解

Floyd算法是一种用于求解所有顶点对之间的最短路径问题的算法,特别适用于稠密图。下面是一个使用C++实现的Floyd算法示例:

#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;
}

在这个示例中:

  1. V 定义了图的顶点数。
  2. graph 是一个二维数组,表示顶点之间的边权重,其中 INT_MAX 表示两个顶点之间没有直接的边。
  3. floyd 函数实现了Floyd算法,计算所有顶点对之间的最短路径,并打印结果。

你可以根据实际需要修改 V 和 graph 的值,以适应不同的图结构。

但是注意:floyd算法的时间复杂度是O(n^{3}),可以处理负数边权的问题,所以时间要求一定要看清楚哦!

相关文章:

floyd算法详解

算法是一种用于求解所有顶点对之间的最短路径问题的算法&#xff0c;特别适用于稠密图。下面是一个使用C实现的算法示例&#xff1a; #include <iostream> #include <climits> // For INT_MAXusing namespace std;const int V 4; // 图的顶点数// 定义一个函数来…...

Web前端性能优化的方向

减少dom渲染复杂列表优化缓存优化首页背景图片加载慢&#xff0c;可以放在服务器上&#xff0c;读取绝对路径900k的图片大小有些大&#xff0c;可以对图片进行压缩&#xff0c;tinypng网站压缩、熊猫压缩、bing域名下的图片url后面带参数w、h、qlt剪裁下拉框数据较多进行懒加载…...

【面试题】设计模式-责任链模式

设计模式-责任链模式 前言责任链简历案例代码小结 前言 我们知道&#xff0c;设计模式是面试时经常被问到的问题之一&#xff0c;这是因为设计模式能够体现出代码设计的美感&#xff0c;且在很多框架的底层也都会使用到各种设计模式&#xff0c;所以对设计模式的考察&#xff…...

JavaEE 第8节 单例模式详解

目录 概念 饿汉模式 懒汉模式 懒汉模式在多线程环境下的优化 1.线程安全问题 2.效率问题 3.指令重排序导致的问题 1&#xff09;为什么要进行指令重排序&#xff1f; 2&#xff09;指令重排序在上述代码为什么会构成问题&#xff1f; 导读&#xff1a; 单例模式是一种…...

OpenAI 发布 GPT-4o 模型安全评估报告:风险等级为“中等”|TodayAI

OpenAI 近日发布了最新的 GPT-4o 系统卡&#xff0c;这是一份研究文件&#xff0c;详细介绍了公司在推出其最新 AI 模型之前所进行的安全措施和风险评估。根据该评估报告&#xff0c;GPT-4o 的总体风险等级被评定为 “中等” 。 GPT-4o 于今年 5 月首次公开发布。在其发布之前…...

学习前端面试知识

2024-8-9 打卡第十天 学习视频链接 js延迟加载 延迟加载&#xff1a;等页面加载完成后再进行加载提高页面加载速度defer属性&#xff0c;同步加载&#xff0c;让脚本与文档同步解析&#xff0c;顺序执行&#xff0c;当文档解析完成再执行defer&#xff0c;执行完再执行脚本&…...

Leetcode JAVA刷刷站(9)回文数

一、题目概述 二、思路方向 在Java中&#xff0c;判断一个整数是否为回文数&#xff0c;可以通过将该整数转换为字符串&#xff0c;然后比较字符串与其反转后的字符串是否相同来实现。但这种方法在整数非常大时可能不太高效&#xff0c;因为它依赖于字符串操作。一个更高效的方…...

数据结构算法

⩕ 单调栈 1、概念 对于一个栈&#xff0c;维持其单调性&#xff0c;有两种情况&#xff0c;单调递增栈&#xff1a;由栈底到栈顶单调递增 单调递减栈&#xff1a;由栈底到栈顶单调递减 2、核心模板&#xff08; 单调递增栈 &#xff09; stack<int> stk; void …...

WordPress个性化站点

这个信息爆炸的时代&#xff0c;拥有一个能够迅速传达信息、展示个性、并能够与世界互动的在线平台&#xff0c;已成为企业和个人的基本需求。WordPress以其无与伦比的易用性和强大的扩展性&#xff0c;成为了构建此类平台的首选工具。而LNMP是由Linux、Nginx、MySQL和PHP组成的…...

GESP C++ 2024年03月一级真题卷

一、单选题&#xff08;每题 2 分&#xff0c;共 30 分&#xff09; 第 1 题 C表达式 (3 - 2) * 3 5 的值是( )。 A. -13 B. 8 C. 2 D. 0 答案&#xff1a;B 解析&#xff1a;略 第 2 题 C 语句 cout << "5%2" << 5 % 2 执行后的输出是…...

Linux驱动开发基础(Hello驱动)

所学内容来自百问网 目录 1. 文件在内核中的表示 2. 打开字符设备节点时&#xff0c;内核中也有对应的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启动可能报错&#xff1a;elasticsearch 7.10启动报错 bootstrap checks failed解决方法问题原因&#xff1a;注意 退出xshell&#xff0c;重新登录&#xff1a; 上面两个配置项改完后&#xff0c;ES启动用户(es 或root) **…...

互联网应用主流框架整合【Redis数据结构及常用命令】

在大部分情况下我们使用Redis只是执行一些简单的命令操作&#xff0c;通常无需区分是否是在一个连接池里的同一个链接去执行&#xff0c;如果需要执行多条命令&#xff0c;需要保证命令在同一个链接里完成&#xff0c;则采用SessionCallback接口操作即可 Redis数据结构-字符串…...

GORM 自动迁移与命名策略

在现代软件开发中&#xff0c;数据库结构的维护和迁移是常见的挑战之一。GORM&#xff0c;作为 Go 语言中强大的 ORM 库&#xff0c;提供了自动迁移功能&#xff0c;帮助开发者轻松地管理数据库表结构的变更。此外&#xff0c;GORM 还允许开发者通过命名策略&#xff08;Naming…...

python社会科学问题研究的计算实验

实验十五&#xff1a;社会科学问题研究的计算实践 1.实验目标及要求 &#xff08;1&#xff09;掌握网络视角 &#xff08;2&#xff09;掌握社会网络基础内容 &#xff08;3&#xff09;掌握友谊悖论 2.实验主要内容 随机生成一次符合社会网络特征的网络&#xff0c;通过计…...

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…...

解释区块链技术的应用场景和优势-水文

区块链技术是一种去中心化的分布式账本技术&#xff0c;其应用场景和优势如下&#xff1a; 金融领域&#xff1a;区块链可以用于加密货币交易&#xff0c;提供安全的、去中心化的支付系统。它也可以用于股票、债券和其他金融交易的记录和结算&#xff0c;提高交易的透明度和效率…...

等保测评基础知识(一)

1、时间类&#xff1a; 网络安全法&#xff1a; 2017年6月1日等保2.0实施时间&#xff1a; 2019年12月1日密码法&#xff1a; 2020年1月1日个人信息保护法&#xff1a; 2021年11月1日&#xff0c;数据安全法实施时间&#xff1a; 2021年9月1日关键信息基础…...

股指期货套期保值中的展期管理有哪些?

在复杂的金融市场环境中&#xff0c;展期作为一种重要的风险管理工具&#xff0c;被广泛应用于期货交易中&#xff0c;特别是当投资者需要对长期资产进行套期保值时。展期的核心思想在于&#xff0c;通过连续替换高流动性的近月期货合约来替代流动性较差的远月合约&#xff0c;…...

如何通过参考文献找到原文

当只有参考文献想要获取原文时&#xff0c;通常会用到以下方法&#xff1a; 举例参考文献1. 杨忠华,周勃,宁宝宽,等.面向新能源产业的专业研究生研创能力培养实践探索——基于“政产学研用”融合驱动[J].高教学刊,2024,10(23):19-22.DOI:10.19980/j.CN23-1593/G4.2024.23.004…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...