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

计算机算法分析与设计(16)---Dijkstra算法(含C++代码)

文章目录

  • 一、知识概述
    • 1.1 算法描述
    • 1.2 例题分析
  • 二、代码编写


一、知识概述

1.1 算法描述

在这里插入图片描述
在这里插入图片描述

1.2 例题分析

在这里插入图片描述

二、代码编写

输入:
 第一行:图的顶点数n
 第二行:图的边数k
 第三行:算法起点begin,算法终点end
 接下来为k行:
 图的点a下标,图的点b下标,a到b的步长len
输出:
 最短距离
样例:
 5
 6
 0 1
 0 2 60
 0 3 30
 0 4 50
 1 2 20
 1 4 10
 3 4 10

#include <iostream>
#include <algorithm>
using namespace std;#define INF 9999999  //定义不可达,即无穷大 
#define MAXN 200     // 最大顶点数//low最短距离,visit访问标记
int begin_idx, end_idx, n, k, map[MAXN][MAXN], low[MAXN], visit[MAXN]; void dijkstra()
{int m_len, index;for (int i = 0; i < n; i++){low[i] = map[begin_idx][i]; //初始化low,表示从源点到其他点的最短距离 }for (int i = 0; i < n; i++){m_len = INF;index = i;for (int j = 0; j < n; j++){   //查找最短未访问距离if (low[j] < m_len && !visit[j]){m_len = low[j];index = j;}}visit[index] = true;for (int j = 0; j < n; j++){int step_len = m_len + map[index][j];if (step_len < low[j]){   //是否更新距离low[j] = step_len;visit[j] = false;}}}cout << "最短距离是:" << endl;cout << low[end_idx] << endl;
}int main()
{int a, b, len;cout<<"请输入顶点数:"<< endl; cin >> n;            // 顶点数cout<<"请输入边数:"<< endl;cin >> k;            // 边数cout<<"请输入要查询的开始和结束下标:"<< endl;cin >> begin_idx >> end_idx; // 始末下标fill(low, low + MAXN, false);     //fill是填充数组值为false fill(visit, visit + MAXN, false); //fill是填充数组值为falsefor (int i = 0; i < MAXN; i++){fill(map[i], map[i] + MAXN, INF); //先填充两顶点间距离为无穷大 }visit[begin_idx] = true;         //开始结点被访问 cout << "请输入两顶点及两顶点间的距离:" << endl; for (int i = 0; i < k; i++){cin >> a >> b >> len; //输入边的值 map[a][b] = map[b][a] = len;}dijkstra();return 0;
} 

在这里插入图片描述

相关文章:

计算机算法分析与设计(16)---Dijkstra算法(含C++代码)

文章目录 一、知识概述1.1 算法描述1.2 例题分析 二、代码编写 一、知识概述 1.1 算法描述 1.2 例题分析 二、代码编写 输入&#xff1a;  第一行&#xff1a;图的顶点数n  第二行&#xff1a;图的边数k  第三行&#xff1a;算法起点begin&#xff0c;算法终点end  接下来…...

小团队之间有哪些好用免费的多人协同办公软件

在小团队协作中&#xff0c;选择适合的多人协同办公软件是提高工作效率和团队协作的重要一环。幸运的是&#xff0c;市场上有许多大多数功能都免费的多人协同办公软件&#xff0c;为小团队提供了强大的协作功能和便捷的工作环境。 在本文中&#xff0c;我将根据自己多年的在线…...

codeforces (C++ Morning)

题目&#xff1a; 翻译&#xff1a; 思路&#xff1a; 1、要将四位数显示&#xff0c;每次操作可以选择移动光标&#xff08;移动到相邻的位置&#xff09;或者显示数字&#xff0c;计算最少需要多少次操作。 2、用flag表示当前光标位置&#xff0c;sum为记录操作次数&#…...

Oracle数据库备份与恢复exp/imp命令

exp导出工具将数据库中数据备份压缩成一个二进制系统文件&#xff0c;可以在不同OS间迁移 可以导出用户所有对象以及对象中的数据&#xff1b;导出用户所有表或者指定的表&#xff1b;导出数据库中所有对象。 imp所执行的步骤&#xff1a; (1) create table --新建表 (2) inser…...

何为心理承受能力?如何提高心理承受能力?

心理承受能力&#xff0c;也可以理解为人的抗压能力&#xff0c;指的是承受压力&#xff0c;承受逆境的能力。人的一生其实就是在不断的解决问题&#xff0c;见招拆招&#xff0c;遇到问题解决问题&#xff0c;在我们不断学习和锻炼的过程中&#xff0c;提高了我们解决问题的效…...

Seata学习

Seata Seata 是一款开源的分布式事务解决方案&#xff0c;致力于在微服务架构下提供高性能和简单易用的分布式事务服务。 官网地址&#xff1a;https://seata.io/zh-cn/index.html 为什么会产生分布式事务&#xff1f; 示例&#xff1a;用户下单后需要创建订单&#xff0c;同时…...

探索数据结构世界之排序篇章(超级详细,你想看的都有)

-文章开头必看 1.&#xff01;&#xff01;&#xff01;本文排序默认都是排升序 2.排序是否稳定值指指排完序之后相同数的相对位置是否改变 3.代码相关解释我都写在注释中了&#xff0c;方便对照着看 1.插入排序1.1直接插入排序1.2希尔排序1.2.1单趟1.2.2多趟基础版——排完一…...

偶数科技发布实时湖仓数据平台Skylab 5.3版本

近日&#xff0c; 偶数发布了最新的实时湖仓数据平台 Skylab 5.3 版本。Skylab包含七大产品&#xff0c;分别为云原生分布式数据库 OushuDB、数据分析与应用平台 Kepler、数据资产管理平台 Orbit、自动化机器学习平台 LittleBoy、数据工厂 Wasp、数据开发与调度平台 Flow、系统…...

vant组件是使用?

首先 在vue项目中使用的时候 要先下载组件 使用npm安装 # Vue 3 项目&#xff0c;安装最新版 Vant npm i vant# Vue 2 项目&#xff0c;安装 Vant 2 npm i vantlatest-v2 使用yarn安装或pnpm # 通过 yarn 安装 yarn add vant# 通过 pnpm 安装 pnpm add vant 在框架中引入即…...

CSP-S 2023 游记

开题&#xff0c;首先先把除了第三题的所有题看了一遍。&#xff08;由于第三题太长&#xff0c;先放着后面再看&#xff09; 决定顺序先把一二题做了。 看第一题&#xff0c;小小思考了一手&#xff0c;发现暴力可做&#xff0c;于是飞速码完&#xff0c;小小对拍一下&#…...

关于Git的入门教程(附GitHub和Gitee的使用方法)

一. Git 概述 Git是一个免费的、开源的分布式版本控制系统&#xff0c;可以快速高效地处理从小型到大型的各种项目。Git易于学习、占地面积小、性能极快。它具有廉价的本地库&#xff0c;方便的暂存区域和多个工作流分支等特性。其性能优于Subversion、CVS、Perforce和ClearCas…...

C# winform如何实现数据的保存和读取

在c#winform中我们在写程序时&#xff0c;经常需要进行数据处理&#xff0c;那么数据如何保存和读取&#xff08;下面我们通过序列化和反序列化的方式来实现&#xff09; 第一步: 我们建立一个winform窗体 第二步: 构建一个外部实体类&#xff08;Student类&#xff09; 第…...

【Java基础面试四十一】、说一说你对static关键字的理解

文章底部有个人公众号&#xff1a;热爱技术的小郑。主要分享开发知识、学习资料、毕业设计指导等。有兴趣的可以关注一下。为何分享&#xff1f; 踩过的坑没必要让别人在再踩&#xff0c;自己复盘也能加深记忆。利己利人、所谓双赢。 面试官&#xff1a;说一说你对static关键字…...

istio介绍(二)

5. kubesphere istio使用 5.1 整体架构 ks-account 提供用户、权限管理相关的 APIks-apiserver 整个集群管理的 API 接口和集群内部各个模块之间通信的枢纽&#xff0c;以及集群安全控制ks-apigateway 负责处理服务请求和处理 API 调用过程中的所有任务ks-console 提供 KubeSp…...

中文编程开发语言工具构件说明:屏幕截取构件的编程操作

屏幕截取 用于截取指定区域的图像。 图 标&#xff1a; 构件类型&#xff1a;不可视 重要属性 l 截取类型 枚举型&#xff0c;设置在截取屏幕时的截取类型。包括&#xff1a;全屏幕、指定区域、活动窗口三种。当全屏幕截取时相当于执行了硬拷屏&#xff08;PrintScre…...

selenium多窗口、多iframe切换、alert、3种等待

1、多标签/多窗口之间的切换 场景&#xff1a; 在页面操作过程中有时候点击某个链接会弹出新的窗口&#xff0c;这时就需要切换到新打开的窗口上进行操作。这种情况下&#xff0c;需要识别多标签或窗口的情况。 操作方法&#xff1a; switch_to.window()方法&#xff1a;切换…...

物联网AI MicroPython传感器学习 之 RTC时钟模块

学物联网&#xff0c;来万物简单IoT物联网&#xff01;&#xff01; 一、产品简介 DS1302 是DALLAS 公司推出的涓流充电时钟芯片&#xff0c;内含有一个实时时钟/日历和31字节静态RAM&#xff0c;实时时钟/日历电路提供秒、分、时、日、周、月、年的信息&#xff0c;每月的天数…...

Mac安装nginx(Homebrew)

查看需要安装 nginx 的信息 brew info nginxDocroot 默认为 /usr/local/var/www 在 /opt/homebrew/etc/nginx/nginx.conf 配置文件中默认端口被配置为8080&#xff0c;从而使 nginx 运行时不需要加 sudo nginx将在 /opt/homebrew//etc/nginx/servers/ 目录中加载所有文件 …...

租用服务器后需要注意什么呢

租用服务器后需要注意什么呢 1、从IDC服务商中接收到服务器时&#xff0c;需要对服务器的各项性能进行测试确认&#xff0c;并做好记录以便对服务器的性能做到心中有数。 2、在服务器租用交接时&#xff0c;要了解服务器的安全设置情况&#xff0c;对服务器安全技术方面不了解…...

pip 时报错 no such option: --bulid-dir 的解决办法

Pycharm 安装第三方库报错及解决方案——no such option: --build-dir Pycharm 安装第三方库报错及解决方案——no such option: --build-dir 最近在学习路径规划相关内容&#xff0c;在运行GitHub上下载例程时缺少“plotly”库&#xff0c;根据网上查到的安装步骤操作&#x…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...