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

Java版-图论-最短路-Floyd算法

实现描述

网络延迟时间示例

在这里插入图片描述

在这里插入图片描述
根据上面提示,可以计算出,最大有100个点,最大耗时为100*wi,即最大的耗时为10000,任何耗时计算出来超过这个值可以理解为不可达了;从而得出实现代码里面的:

int maxTime = 10005; //这里是题目给出的最大距离
  1. 定义数组w[i][j]=weight; 其中,表示从i->j需要耗时weight;
  2. 求解从k出发,到其他各个点的最短时间,需要算出从k出发到其余各个点的时间取最大值;
  3. 利用中间点middle,从i->j的距离,如果经过中间点middle,则w[i][j]=w[i][middle]+w[middle][j];
  4. 利用状态转移,可以dp出w的矩阵值,然后计算从k出发到各个点的时间,进而求出时间的最大值;

实现代码

 public static void main(String[] args) {
//        int[][] times = {
//                {2, 1, 1},
//                {2, 3, 1},
//                {3, 4, 1}};
//        int n = 4; //4个节点
//        int k = 2; //从2int[][] times = {{1, 2, 1}};int n = 2; int k = 2; System.out.println(new Floyd().networkDelayTime(times, n, k));}int[][] matrix;public int networkDelayTime(int[][] times, int n, int k) {int result = -1;matrix = new int[n + 1][n + 1];int maxTime = 10005; //这里是题目给出的最大距离for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) {matrix[i][j] = 0;} else {matrix[i][j] = maxTime;}}}//初始化矩阵实际值for (int[] time : times) {int from = time[0], to = time[1];matrix[from][to] = time[2];}floydAlgorithm(n, matrix);for (int i = 1; i <= n; i++) {result = Math.max(result, matrix[k][i]);}return result >= maxTime ? -1 : result;}void floydAlgorithm(int n, int[][] matrix) {for (int middle = 1; middle <= n; middle++) {  //中转点for (int i = 1; i <= n; i++) { //起点for (int j = 1; j <= n; j++) { //终点matrix[i][j] = Math.min(matrix[i][j], matrix[i][middle] + matrix[middle][j]);}}}}

相关文章:

Java版-图论-最短路-Floyd算法

实现描述 网络延迟时间示例 根据上面提示&#xff0c;可以计算出&#xff0c;最大有100个点&#xff0c;最大耗时为100*wi,即最大的耗时为10000&#xff0c;任何耗时计算出来超过这个值可以理解为不可达了&#xff1b;从而得出实现代码里面的&#xff1a; int maxTime 10005…...

可视化建模以及UML期末复习篇----UML图

这是一篇相对较长的文章&#xff0c;如你们所见&#xff0c;比较详细&#xff0c;全长两万字。我不建议你们一次性看完&#xff0c;直接跳目录找你需要的知识点即可。 --------欢迎各位来到我UML国&#xff01; 一、UML图 总共有如下几种&#xff1a; 用例图&#xff08;Use Ca…...

HTML常见标签列表,涵盖了多种用途的标签。

文档结构标签 <!DOCTYPE html>&#xff1a;声明文档类型&#xff0c;告诉浏览器使用HTML5标准。<html>&#xff1a;HTML文档的根元素。<head>&#xff1a;包含文档的元数据&#xff08;meta-data&#xff09;&#xff0c;如标题、字符集、样式表链接、脚本等…...

FPGA 16 ,Verilog中的位宽:深入理解与应用

目录 前言 一. 位宽的基本概念 二. 位宽的定义方法 1. 使用向量变量定义位宽 ① 向量类型及位宽指定 ② 位宽范围及位索引含义 ③ 存储数据与字节数据 2. 使用常量参数定义位宽 3. 使用宏定义位宽 4. 使用[:][-:]操作符定义位宽 1. 详细解释 : 操作符 -: 操作符 …...

vue-生命周期

Vue 的生命周期是指 Vue 实例从创建到销毁期间经历的一系列阶段。每个阶段都有相应的钩子函数&#xff08;Lifecycle Hooks&#xff09;&#xff0c;允许开发者在这些关键时刻执行自定义逻辑。 一、钩子函数 1. 创建阶段 beforeCreate 在实例初始化之后&#xff0c;数据观测 …...

浅谈Kubernetes(K8s)之RC控制器与RS控制器

1.RC控制器 1.1RC概述 Replication Controller 控制器会持续监控正在运行的Pod列表&#xff0c;并保证相应类型的Pod的数量与期望相符合&#xff0c;如果Pod数量过少&#xff0c;它会根据Pod模板创建新的副本&#xff0c;反之则会删除多余副本。通过RC可实现了应用服务的高可用…...

本题要求采用选择法排序,将给定的n个整数从大到小排序后输出。

#include <stdio.h> #define MAXN 10 int main() { int i, index, k, n, temp; int a[MAXN]; scanf("%d", &n); for (i 0; i < n; i) { scanf("%d", &a[i]); } // 外层循环控制排序轮数&#xff0c;一共需要n-1轮 for (k 0; k < n…...

Linux: glibc: 频繁调用new/delete会不会导致内存的碎片

最近同事问了一个问题:频繁调用new/delete会不会导致内存的碎片。 下面是我想到的一些回答, glibc的内存处理机制,是在释放的时候会自动将小块内存整合成大块内存,为接下来满足大块的需求的可能。而且程序也不是一直占着内存不释放(如果是一直不释放,要考虑是不是内存泄漏…...

量子变分算法---损失函数

引子 关于损失函数&#xff0c;我们知道在强化学习中&#xff0c;会有一个函数&#xff0c;用来表示模型每一次行为的分数&#xff0c;通过最大化得分&#xff0c;建立一个正反馈机制&#xff0c;若模型为最优则加分最多&#xff0c;若决策不佳则加很少分或者扣分。而在神经网络…...

计算机的性能评估

目录 计算机的性能评估 确定性能指标 考虑通讯因素 考虑机器过热因素 综合评估模型 动态评估与调整 计算机的性能评估 在分布式计算机系统中,综合考虑各种因素来评估性能是一个复杂但重要的问题。以下是一种可能的方法来综合考虑评估分布式计算机性能,动态地考虑实际情…...

大数据之国产数据库_OceanBase数据库002_在centos7.9上_安装部署OceanBase001_踩坑指南_亲测可用

部署前最好看一下,部署前的要求, 主要是系统 以及系统内核版本,还有比如清理一下缓存等,按照做一做. 这些都是前置条件. 清一下缓存. 也就是说官网给的前置的条件,都要根据说明去执行一遍,如果不执行可能后面安装会报错. 然后用户最好也去创建一个用户. 注意前置...

【ETCD】【源码阅读】深入解析 EtcdServer.run 函数

EtcdServer.run 是 etcd 的核心运行逻辑之一&#xff0c;负责管理 Raft 状态机的应用、事件调度以及集群的核心操作。本文将逐步从源码层面分析 run 函数的逻辑&#xff0c;帮助读者理解其内部机制和设计思想。 函数签名与关键职责 func (s *EtcdServer) run() {... }关键职责…...

springboot/ssm校内订餐系统Java代码web项目美食外卖点餐配送源码

springboot/ssm校内订餐系统Java代码web项目美食外卖点餐配送源码 基于springboot(可改ssm)vue项目 开发语言&#xff1a;Java 框架&#xff1a;springboot/可改ssm vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff…...

floodfill算法

目录 什么是floodfill算法 题目一——733. 图像渲染 - 力扣&#xff08;LeetCode&#xff09; 题目二——200. 岛屿数量 - 力扣&#xff08;LeetCode&#xff09; 题目三——695. 岛屿的最大面积 - 力扣&#xff08;LeetCode&#xff09; 题目四—— 130. 被围绕的区域 …...

【JAVA】六亮增加贴

James Gosling&#xff08;詹姆斯.高斯林&#xff09; Java 语言源于 1991 年 4 月&#xff0c;Sun 公司 James Gosling博士 领导的绿色计划(Green Project) 开始启动&#xff0c;此计划最初的目标是开发一种能够在各种消费性电子产品(如机顶盒、冰箱、收音机等)上运行的程序…...

git提交时出现merge branch main of xxx

git提交时出现merge branch main of xxx 原因&#xff1a; 1、同事commit了一个修改A&#xff0c;push到remote 2、我把这个修改直接pull了下来&#xff08;pull是fetchmerge的操作&#xff0c;自动合并到本地workspace&#xff09; 3、同事因为后续的commit有冲突&#xff0c…...

lstm 输入数据的形状是怎么样的,他有两种输入方式,通过参数 batch_first来设置 默认是False

lstm 输入数据的形状是怎么样的&#xff0c;他有两种输入方式&#xff0c;通过参数 batch_first来设置 默认是False 当batch_firstFalse时&#xff0c;LSTM输入的数据形状通常是一个三维张量&#xff0c;其维度顺序为[sequence_length, batch_size, input_size]。下面是对这些维…...

Apache Doris 数据类型

Apache Doris 已支持的数据类型列表如下&#xff1a; 数值类型​ 类型名存储空间&#xff08;字节&#xff09;描述BOOLEAN1布尔值&#xff0c;0 代表 false&#xff0c;1 代表 true。TINYINT1有符号整数&#xff0c;范围 [-128, 127]。SMALLINT2有符号整数&#xff0c;范围 …...

编译问题 fatal error: rpc/rpc.h: No such file or directory

在编译一些第三方软件的时候&#xff0c;会经常遇到一些文件识别不到的问题&#xff0c;这里整理下做个归总。 目前可能的原因有&#xff08;排序分先后&#xff09;&#xff1a; 文件不存在&#xff1b;文件存在但路径识别不了&#xff1b;…… 这次以常见的编译lmbench测试…...

linux 安装composer

下载composer curl -sS https://getcomposer.org/installer | php下载后设置环境变量&#xff0c;直接通过命令composer -v mv composer.phar /usr/local/bin/composer查看版本看是否安装成功 composer -v...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...