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

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...