当前位置: 首页 > 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.读入数据总结前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

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

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

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...