计算机算法分析与设计(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 例题分析 二、代码编写 输入: 第一行:图的顶点数n 第二行:图的边数k 第三行:算法起点begin,算法终点end 接下来…...
小团队之间有哪些好用免费的多人协同办公软件
在小团队协作中,选择适合的多人协同办公软件是提高工作效率和团队协作的重要一环。幸运的是,市场上有许多大多数功能都免费的多人协同办公软件,为小团队提供了强大的协作功能和便捷的工作环境。 在本文中,我将根据自己多年的在线…...
codeforces (C++ Morning)
题目: 翻译: 思路: 1、要将四位数显示,每次操作可以选择移动光标(移动到相邻的位置)或者显示数字,计算最少需要多少次操作。 2、用flag表示当前光标位置,sum为记录操作次数&#…...
Oracle数据库备份与恢复exp/imp命令
exp导出工具将数据库中数据备份压缩成一个二进制系统文件,可以在不同OS间迁移 可以导出用户所有对象以及对象中的数据;导出用户所有表或者指定的表;导出数据库中所有对象。 imp所执行的步骤: (1) create table --新建表 (2) inser…...
何为心理承受能力?如何提高心理承受能力?
心理承受能力,也可以理解为人的抗压能力,指的是承受压力,承受逆境的能力。人的一生其实就是在不断的解决问题,见招拆招,遇到问题解决问题,在我们不断学习和锻炼的过程中,提高了我们解决问题的效…...
Seata学习
Seata Seata 是一款开源的分布式事务解决方案,致力于在微服务架构下提供高性能和简单易用的分布式事务服务。 官网地址:https://seata.io/zh-cn/index.html 为什么会产生分布式事务? 示例:用户下单后需要创建订单,同时…...
探索数据结构世界之排序篇章(超级详细,你想看的都有)
-文章开头必看 1.!!!本文排序默认都是排升序 2.排序是否稳定值指指排完序之后相同数的相对位置是否改变 3.代码相关解释我都写在注释中了,方便对照着看 1.插入排序1.1直接插入排序1.2希尔排序1.2.1单趟1.2.2多趟基础版——排完一…...
偶数科技发布实时湖仓数据平台Skylab 5.3版本
近日, 偶数发布了最新的实时湖仓数据平台 Skylab 5.3 版本。Skylab包含七大产品,分别为云原生分布式数据库 OushuDB、数据分析与应用平台 Kepler、数据资产管理平台 Orbit、自动化机器学习平台 LittleBoy、数据工厂 Wasp、数据开发与调度平台 Flow、系统…...
vant组件是使用?
首先 在vue项目中使用的时候 要先下载组件 使用npm安装 # Vue 3 项目,安装最新版 Vant npm i vant# Vue 2 项目,安装 Vant 2 npm i vantlatest-v2 使用yarn安装或pnpm # 通过 yarn 安装 yarn add vant# 通过 pnpm 安装 pnpm add vant 在框架中引入即…...
CSP-S 2023 游记
开题,首先先把除了第三题的所有题看了一遍。(由于第三题太长,先放着后面再看) 决定顺序先把一二题做了。 看第一题,小小思考了一手,发现暴力可做,于是飞速码完,小小对拍一下&#…...
关于Git的入门教程(附GitHub和Gitee的使用方法)
一. Git 概述 Git是一个免费的、开源的分布式版本控制系统,可以快速高效地处理从小型到大型的各种项目。Git易于学习、占地面积小、性能极快。它具有廉价的本地库,方便的暂存区域和多个工作流分支等特性。其性能优于Subversion、CVS、Perforce和ClearCas…...
C# winform如何实现数据的保存和读取
在c#winform中我们在写程序时,经常需要进行数据处理,那么数据如何保存和读取(下面我们通过序列化和反序列化的方式来实现) 第一步: 我们建立一个winform窗体 第二步: 构建一个外部实体类(Student类) 第…...
【Java基础面试四十一】、说一说你对static关键字的理解
文章底部有个人公众号:热爱技术的小郑。主要分享开发知识、学习资料、毕业设计指导等。有兴趣的可以关注一下。为何分享? 踩过的坑没必要让别人在再踩,自己复盘也能加深记忆。利己利人、所谓双赢。 面试官:说一说你对static关键字…...
istio介绍(二)
5. kubesphere istio使用 5.1 整体架构 ks-account 提供用户、权限管理相关的 APIks-apiserver 整个集群管理的 API 接口和集群内部各个模块之间通信的枢纽,以及集群安全控制ks-apigateway 负责处理服务请求和处理 API 调用过程中的所有任务ks-console 提供 KubeSp…...
中文编程开发语言工具构件说明:屏幕截取构件的编程操作
屏幕截取 用于截取指定区域的图像。 图 标: 构件类型:不可视 重要属性 l 截取类型 枚举型,设置在截取屏幕时的截取类型。包括:全屏幕、指定区域、活动窗口三种。当全屏幕截取时相当于执行了硬拷屏(PrintScre…...
selenium多窗口、多iframe切换、alert、3种等待
1、多标签/多窗口之间的切换 场景: 在页面操作过程中有时候点击某个链接会弹出新的窗口,这时就需要切换到新打开的窗口上进行操作。这种情况下,需要识别多标签或窗口的情况。 操作方法: switch_to.window()方法:切换…...
物联网AI MicroPython传感器学习 之 RTC时钟模块
学物联网,来万物简单IoT物联网!! 一、产品简介 DS1302 是DALLAS 公司推出的涓流充电时钟芯片,内含有一个实时时钟/日历和31字节静态RAM,实时时钟/日历电路提供秒、分、时、日、周、月、年的信息,每月的天数…...
Mac安装nginx(Homebrew)
查看需要安装 nginx 的信息 brew info nginxDocroot 默认为 /usr/local/var/www 在 /opt/homebrew/etc/nginx/nginx.conf 配置文件中默认端口被配置为8080,从而使 nginx 运行时不需要加 sudo nginx将在 /opt/homebrew//etc/nginx/servers/ 目录中加载所有文件 …...
租用服务器后需要注意什么呢
租用服务器后需要注意什么呢 1、从IDC服务商中接收到服务器时,需要对服务器的各项性能进行测试确认,并做好记录以便对服务器的性能做到心中有数。 2、在服务器租用交接时,要了解服务器的安全设置情况,对服务器安全技术方面不了解…...
pip 时报错 no such option: --bulid-dir 的解决办法
Pycharm 安装第三方库报错及解决方案——no such option: --build-dir Pycharm 安装第三方库报错及解决方案——no such option: --build-dir 最近在学习路径规划相关内容,在运行GitHub上下载例程时缺少“plotly”库,根据网上查到的安装步骤操作&#x…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
