计算机算法分析与设计(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…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...
【Java】Ajax 技术详解
文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...
