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

实验三 贪心算法

实验三  贪心算法

迪杰斯特拉的贪心算法实现

优先队列等

1.实验目的

1、掌握贪心算法的基本要素 :最优子结构性质和贪心选择性质

2、应用优先队列求单源顶点的最短路径Dijkstra算法,掌握贪心算法。

2.实验环境

Java

3.问题描述

给定带权有向图G =(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

4.复杂度分析

 Dijkstra算法的时间复杂度为O((m+n)logn),其中m是边的数量,n是顶点的数量。

5.代码实现

package shiyan3_3;import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;public class DijkstraAlgorithm {public static void main(String[] args) throws IOException {runDijkstraAlgorithm("input.txt", "output.txt");}private static class Result {int dist;List<Integer> path;public Result(int dist, List<Integer> path) {this.dist = dist;this.path = path;}}public static void runDijkstraAlgorithm(String inputFile, String outputFile) throws IOException {BufferedReader reader = new BufferedReader(new FileReader(inputFile));String[] input = reader.readLine().split(" ");int n = Integer.parseInt(input[0]);int m = Integer.parseInt(input[1]);List<Edge>[] graph = new List[n + 1];for (int i = 1; i <= n; i++) {graph[i] = new ArrayList<>();}for (int i = 0; i < m; i++) {input = reader.readLine().split(" ");int u = Integer.parseInt(input[0]);int v = Integer.parseInt(input[1]);int w = Integer.parseInt(input[2]);graph[u].add(new Edge(v, w));}reader.close();int s = 1;Result[] results = new Result[n + 1];PriorityQueue<Node> pq = new PriorityQueue<>();for (int i = 1; i <= n; i++) {if (i == s) continue;int[] dist = new int[n + 1];int[] pre = new int[n + 1];Arrays.fill(dist, Integer.MAX_VALUE);Arrays.fill(pre, -1);dist[s] = 0;pq.offer(new Node(s, 0));while (!pq.isEmpty()) {Node curr = pq.poll();if (curr.dist != dist[curr.u]) continue;for (Edge edge : graph[curr.u]) {int v = edge.v;int weight = edge.weight;if (dist[v] > dist[curr.u] + weight) {dist[v] = dist[curr.u] + weight;pre[v] = curr.u;pq.offer(new Node(v, dist[v]));}}}List<Integer> path = new ArrayList<>();if (pre[i] != -1) getPath(i, pre, path);if (path.size() > 0) path.add(0, s);results[i] = new Result(dist[i], path);}PrintWriter writer = new PrintWriter(new FileWriter(outputFile));writer.println("起点\t终点\t最短路径\t\t\t最短路径长度");for (int i = 1; i <= n; i++) {if (i == s) continue;String res = s + "\t" + i + "\t";if (results[i] == null || results[i].path.size() == 0) {res += "NA\t\t\tNA";} else {String path = results[i].path.stream().map(Object::toString).collect(Collectors.joining("->"));int padding = 32 - path.length();if (padding > 0) path += String.format("%" + padding + "s", "");res += path + "\t" + results[i].dist;}writer.println(res);}writer.close();System.out.println("输出成功!");}private static void getPath(int u, int[] pre, List<Integer> path) {if (u == -1) return;getPath(pre[u], pre, path);path.add(u);}private static class Node implements Comparable<Node> {int u;int dist;public Node(int u, int dist) {this.u = u;this.dist = dist;}@Overridepublic int compareTo(Node other) {return Integer.compare(this.dist, other.dist);}}private static class Edge {int v;int weight;public Edge(int v, int weight) {this.v = v;this.weight = weight;}}
}

输入 

运行

 输出

相关文章:

实验三 贪心算法

实验三 贪心算法 迪杰斯特拉的贪心算法实现 优先队列等 1.实验目的 1、掌握贪心算法的基本要素 &#xff1a;最优子结构性质和贪心选择性质 2、应用优先队列求单源顶点的最短路径Dijkstra算法&#xff0c;掌握贪心算法。 2.实验环境 Java 3.问题描述 给定带权有向图G (V…...

详解go的hex.Encode原理

简言 今天看nsq的messageID生成的时候&#xff0c;发现它使用了hex.Encode函数来产生编码&#xff0c;那就顺道研究一下这个编码方式。 原理 hex是16进制的意思&#xff0c;encode是进行编码的意思&#xff0c;内部实现也很简单&#xff0c;就是 每4位计算出十六进制的值&a…...

R730服务器用光盘安装系统(Esxi系统)

准备阶段&#xff1a;dell R730服务器&#xff0c;本教程一般适用于dell所有服务器&#xff0c;移动光盘&#xff0c;光碟做好镜像系统。在这里我安装的系统是Esxi系统&#xff0c;其他操作系统类似&#xff0c;只是安装的步骤不一样而已。 1、将系统盘插入光驱(移动光盘)&…...

SpringCloud nacos 集成 gateway ,实现动态路由

&#x1f388; 作者&#xff1a;Linux猿 &#x1f388; 简介&#xff1a;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;Linux、C/C、云计算、物联网、面试、刷题、算法尽管咨询我&#xff0c;关注我&#xff0c;有问题私聊&#xff01; &…...

flutter:角标

角标应该非常常见了&#xff0c;以小说app为例&#xff0c;通常会在小说封面的右上角上显示当前未读的章数。 badges 简介 Flutter的badges库是一个用于创建徽章组件的开源库。它提供了简单易用的API&#xff0c;使开发者可以轻松地在Flutter应用程序中添加徽章效果。 官方文…...

基于JAVA SpringBoot和Vue高考志愿填报辅助系统

随着信息技术在管理中的应用日益深入和广泛&#xff0c;管理信息系统的实施技术也越来越成熟&#xff0c;管理信息系统是一门不断发展的新学科&#xff0c;任何一个机构要想生存和发展&#xff0c;要想有机、高效地组织内部活动&#xff0c;就必须根据自身的特点进行管理信息时…...

[php-cos]ThinkPHP项目集成腾讯云储存对象COS

Cos技术文档 1、安装phpSdk 通过composer的方式安装。 1.1 在composer.json中添加 qcloud/cos-sdk-v5: >2.0 "require": {"php": ">7.2.5","topthink/framework": "^6.1.0","topthink/think-orm": "…...

DuckDB全面挑战SQLite

概要 当我们想要在具有嵌入式数据库的本地环境中工作时&#xff0c;我们倾向于默认使用 SQLite。虽然大多数情况下这都很好&#xff0c;但这就像骑自行车去 100 公里之外&#xff1a;可能不是最好的选择。 这篇文章中将讨论以下要点&#xff1a; • DuckDB 简介&#xff1a;它…...

Elasticsearch查询裁剪

如果source有成千上百个字段,查询的数据没法看 某些敏感字段不能随意展示 响应数据较大影响网络带宽 查看文档信息 查看ffbf索引id为123的文档信息 GET /ffbf/_doc/123返回结果 {"_index" : "ffbf","_type" : "_doc","_id&qu…...

Hadoop——Hive运行环境搭建

Windows&#xff1a;10 JDK&#xff1a;1.8 Apache Hadoop&#xff1a;2.7.0 Apache Hive&#xff1a;2.1.1 Apache Hive src&#xff1a;1.2.2 MySQL&#xff1a;5.7 1、下载 Hadoop搭建 Apache Hive 2.1.1&#xff1a;https://archive.a…...

(vue)vue项目中引入外部字体

(vue)vue项目中引入外部字体 效果&#xff1a; 第一步 放置字体包&#xff0c;在assets下创建一个fonts文件夹&#xff0c;放入下载的字体文件 第二步 创建一个font.css文件用于定义这个字体包的名字 第三步 在App.vue的css中将这个css文件引入 第四步 页面使用 font-famil…...

ChatGPT在语义理解和信息提取中的应用如何?

ChatGPT在语义理解和信息提取领域有着广泛的应用潜力。语义理解是指对文本进行深层次的理解&#xff0c;包括词义、句义和篇章义等层面的理解。信息提取是指从文本中自动抽取结构化的信息&#xff0c;如实体、关系、事件等。ChatGPT作为一种预训练语言模型&#xff0c;具有丰富…...

Mysql-主从复制与读写分离

Mysql 主从复制、读写分离 一、前言&#xff1a;二、主从复制原理1.MySQL的复制类型2. MySQL主从复制的工作过程;3.MySQL主从复制延迟4. MySQL 有几种同步方式&#xff1a;5.Mysql应用场景 三、主从复制实验1.主从服务器时间同步1.1 master服务器配置1.2 两台SLAVE服务器配置 2…...

算法练习(3):牛客在线编程04 堆/栈/队列

package jz.bm;import java.util.*;public class bm4 {/*** BM42 用两个栈实现队列*/Stack<Integer> stack1 new Stack<>();Stack<Integer> stack2 new Stack<>();public void push(int node) {stack1.push(node);}public int pop() {while (!stack1…...

mac下安装vue cli脚手架并搭建一个简易项目

目录 1、确定本电脑下node和npm版本是否为项目所需版本。 2、下载vue脚手架 3、创建项目 1、下载node。 如果有node&#xff0c;打开终端&#xff0c;输入node -v和npm -v , 确保node和npm的版本&#xff0c;(这里可以根据自己的需求去选择&#xff0c;如果对最新版本的内容有…...

尝试-InsCode Stable Diffusion 美图活动一期

一、 Stable Diffusion 模型在线使用地址&#xff1a; https://inscode.csdn.net/inscode/Stable-Diffusion 二、模型相关版本和参数配置&#xff1a; 活动地址 三、图片生成提示词与反向提示词&#xff1a; 提示词&#xff1a;realistic portrait painting of a japanese…...

【OpenGL学习】之着色器GLSL基础

基本类型: 类型说明void空类型,即不返回任何值bool布尔类型 true,falseint带符号的整数 signed integerfloat带符号的浮点数 floating scalarvec2, vec3, vec4n维浮点数向量 n-component floating point vectorbvec2, bvec3, bvec4n维布尔向量 Boolean vectorivec2, ivec3, iv…...

Python爬虫基础知识点有哪些

目录 Python爬虫基础知识点 Requests库 Beautiful Soup库 正则表达式 数据存储 防止被反爬虫策略 爬虫调度和任务管理 认识robots.txt文件 反爬虫法律与道德 示例代码 Requests库 Beautiful Soup库 正则表达式 数据存储 防止被反爬虫策略 结语 网络世界中信息的…...

【CSS】 vh、rem 和 px 的区别

vh、rem 和 px 都是 CSS 中常见的长度单位&#xff0c;它们有以下区别&#xff1a; px&#xff08;像素&#xff09;是一个绝对单位&#xff0c;表示屏幕上的实际像素点。它的大小不会根据设备或浏览器的设置进行调整&#xff0c;是一个固定值。 rem&#xff08;根元素字体大小…...

如何设置板子从emmc启动-针对imx6ull

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...

作为点的对象CenterNet论文阅读

摘要 检测器将图像中的物体表示为轴对齐的边界框。大多数成功的目标检测方法都会枚举几乎完整的潜在目标位置列表&#xff0c;并对每一个位置进行分类。这种做法既浪费又低效&#xff0c;并且需要额外的后处理。在本文中&#xff0c;我们采取了不同的方法。我们将物体建模为单…...