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

Dijkstra算法求解最短路径 自写代码

#include <iostream>
#define Max 503
#define INF 0xcffffffusing namespace std;typedef struct AMGraph {							//定义图int vex, arc;int arcs[Max][Max];								//邻接矩阵
};int dist[Max], path[Max];							//dis保存最短路径总权值、path通过保存路径的前驱结点来保存路径
bool final[Max];										//已找到最短路集合int distmin(AMGraph& G) {int flag = 0;int min = INF;for (int i = 1; i <= G.vex; i++) {if (final[i] == false && min > dist[i]) {min = dist[i];flag = i;}}return flag;
}void Dijkstra(AMGraph& G,int x)							//迪杰斯特拉算法
{for (int i = 1; i <= G.vex; i++) {if (i != x) dist[i] = INF;else dist[i] = 0;}memset(final, 0, sizeof(final));memset(path, -1, sizeof(path));for (int i = 1; i <= G.vex - 1; i++) {int minflag = distmin(G);final[minflag] = true;for (int j = 1; j <= G.vex; j++) {if (G.arcs[minflag][j] > 0) {if (dist[minflag] + G.arcs[minflag][j] < dist[j]) {dist[j] = dist[minflag] + G.arcs[minflag][j];path[j] = minflag;}}}}}void find(int x)									//递归输出最短路径
{if (path[x] == -1) {cout << x;}else {find(path[x]);cout << " -> " << x;}return;
}void putin(AMGraph& G)								//输入图
{cin >> G.vex >> G.arc;for (int i = 1; i <= G.vex; i++)				//初始化邻接矩阵for (int j = 1; j <= G.vex; j++)G.arcs[i][j] = INF;for (int i = 1; i <= G.arc; i++){int u, v, w;cin >> u >> v >> w;G.arcs[u][v] = w;}
}void putout(AMGraph& G,int x)								//输出
{//cout << "起点 v1 到各点的最短路程为: \n";for (int i = 1; i < G.vex; i++){cout << dist[i] << " ";}cout << dist[G.vex] << endl;for (int i = 1; i <= G.vex; i++){if (i != x) {cout << "起点 v"<<x<<" 到 v" << i << " 的路径为: ";find(i);cout <<"带权路径长度是"<< dist[i];cout << endl;}}
}int main()
{AMGraph G;putin(G);int point = 3;//要算的是point点到其他点的距离Dijkstra(G,point);putout(G,point);return 0;
}
/*测试数据,王道2025版p243的图。
5 10
1 2 10
1 5 5
2 5 2
5 2 3
2 3 1
5 3 9
5 4 2
3 4 4
4 3 6
4 1 7
*/

http://t.csdnimg.cn/aaE07icon-default.png?t=N7T8http://t.csdnimg.cn/aaE07参考文章如上,另外进行了一点改进。

相关文章:

Dijkstra算法求解最短路径 自写代码

#include <iostream> #define Max 503 #define INF 0xcffffffusing namespace std;typedef struct AMGraph { //定义图int vex, arc;int arcs[Max][Max]; //邻接矩阵 };int dist[Max], path[Max]; //dis保存最短路径总权值、path通过保存路径的前驱结…...

C#如何对某个词在字符串中出现的次数进⾏计数(LINQ)

文章目录 基础知识实现方法基础计数LINQ优化处理标点符号总结 LINQ&#xff08;Language-Integrated Query&#xff09;是C#和VB.NET中强大的查询语言&#xff0c;它可以用来查询集合、SQL数据库、XML文档等。在C#中&#xff0c;我们可以使用LINQ来简化对字符串中特定单词出现次…...

Linux篇之OS层内核参数的调优

Linux内核参数调优 Linux 内核参数的调优和分类是一个复杂的主题&#xff0c;这涉及到系统性能、稳定性和安全性等多个方面。 内核参数主要可以分为以下几类&#xff1a; 1. 内核参数的分类 1.1 系统性能参数 这些参数影响系统的整体性能&#xff0c;包括 CPU 调度、内存管理…...

DLMS/COSEM中的信息安全:安全密钥(上)

加密密钥是一个参数,和加密算法一起使用,加密算法决定了这样一种方式,带有密钥的实体,可以重现和进行逆操作,而没有密钥则不能。对DLMS/COSEM的用途,操作的例子包含: ——明文转换成密文; ——密文转换成明文; ——计算和验证认证码(MAC); …...

Taro基础知识学习

一、安装及使用 CLI工具安装 需要使用 npm 或者 yarn 全局安装 tarojs/cli //使用 npm 安装 CLI npm install -g tarojs/cli//使用 yarn 安装 CLI yarn global add tarojs/cli//使用 cnpm 安装 CLI cnpm install -g tarojs/cli//使用npm info查看Taro的版本信息 npm info ta…...

浮点型在内存中的存储

前言 在上一期中我们讲到了有关于整型在内存中的存储&#xff0c;新朋友可以点开&#x1f517;了解一下&#xff0c;那这一期中我们将讲到的浮点数是不是存储方式和整型一致呢&#xff1f; 一、浮点数在内存中的存储 为了探究这个问题我们先来看一段代码 #include<stdio…...

微信小程序之behaviors

目录 概括 Demo演示 进阶演示 1. 若具有同名的属性或方法 2. 若有同名的数据 3. 若有同名的生命周期函数 应用场景 最后 属性&方法 组件中使用 代码示例&#xff1a; 同名字段的覆盖和组合规则 概括 一句话总结: behaviors是用于组件间代码共享的特性, 类似一…...

java.lang.NoClassDefFoundError: ch/qos/logback/core/util/StatusPrinter2

1、问题 SpringBoot升级报错&#xff1a; Exception in thread "main" java.lang.NoClassDefFoundError: ch/qos/logback/core/util/StatusPrinter2 类找不到&#xff1a; Caused by: java.lang.ClassNotFoundException: ch.qos.logback.core.util.StatusPrinter22、…...

WebRTC ICE配置类型

ICE&#xff08;Interactive Connectivity Establishment&#xff09;是一个用于建立WebRTC和其他实时通信会话中的点对点连接的框架。ICE协议通过尝试多个候选地址&#xff08;候选者&#xff09;来寻找最佳路径来连接两个对等端。ICE有多种配置类型&#xff0c;包括标准ICE、…...

制造知识普及(八)--企业内部物料编码(IPN)与制造商物料编码(MPN)

1、什么是物料编码 通常情况下&#xff0c;物料编码分两种&#xff0c;一种是企业内部物料编码&#xff08;IPN&#xff09;&#xff0c;由于在企业研发制造和生产中确认物料唯一性的&#xff0c;用于承载设计参数要求和技术要求。另一种是制造商物料编码&#xff08;MPN&…...

大模型学习笔记 - InstructGPT中的微调与对齐

LLM 微调 之 InstructGPT中的微调与对齐 LLM 微调 之 InstructGPT中的微调与对齐 技术概览 InstructGPT中的微调与对齐 大体步骤标注数据量模型训练 1. SFT 是如何训练的2. Reward Model是如何训练的3. RLHF 是如何训练的具体讲解RLHF 的loss 函数 模型效果参考链接&#xf…...

Unity近似的Transform实现

Unity近似的Transform实现 #include <stdint.h> #include<iomanip> #include <sstream>#include "Transform.h"//Transform::Transform(const Transform& a){ // LOGW("xww 2"); //}Transform::Transform(glm::vec3 localPositio…...

openvidu私有化部署

openvidu私有化部署 简介 OpenVidu 是一个允许您实施实时应用程序的平台。您可以从头开始构建全新的 OpenVidu 应用程序&#xff0c;但将 OpenVidu 集成到您现有的应用程序中也非常容易。 OpenVidu 基于 WebRTC 技术&#xff0c;允许开发您可以想象的任何类型的用例&#xf…...

基于深度学习的视频伪造检测

基于深度学习的视频伪造检测旨在利用深度学习技术来检测和识别伪造的视频内容。伪造视频&#xff0c;尤其是深伪&#xff08;Deepfake&#xff09;视频&#xff0c;近年来随着生成对抗网络&#xff08;GAN&#xff09;技术的发展&#xff0c;变得越来越逼真和难以识别。这对个人…...

python机器人编程——开发一个pymatlab工具箱(上)

目录 一、前言二、实现过程2.1 封装属性2.2 数据流化显示2.3 输入数据的适应性 三、核心代码说明3.1 设置缓存3.2 随机信号3.3 根据设置绘图 五、总结四、源码PS.扩展阅读ps1.六自由度机器人相关文章资源ps2.四轴机器相关文章资源ps3.移动小车相关文章资源 一、前言 我们知道m…...

输入类控件

目录 1.Line Edit 代码示例: 录入个人信息 代码示例: 使用正则表达式验证输入框的数据 代码示例: 验证两次输入的密码一致 代码示例: 切换显示密码 2.Text Edit 代码示例: 获取多行输入框的内容 代码示例: 验证输入框的各种信号 3.Combo Box 代码示例: 使用下拉框模拟…...

C++20中的模块

大多数C项目使用多个翻译单元(translation units)&#xff0c;因此它们需要在这些单元之间共享声明和定义(share declarations and definitions)。headers的使用在这方面非常突出。模块(module)是一种language feature&#xff0c;用于在翻译单元之间共享声明和定义。它们是某些…...

Selenium与流行框架集成:pytest与Allure报告

Selenium与流行框架集成&#xff1a;pytest与Allure报告 在现代软件开发中&#xff0c;自动化测试是确保产品质量和快速迭代的关键。Selenium作为业界领先的Web自动化测试工具&#xff0c;其灵活性和强大的功能受到广泛认可。为了进一步提升测试效率和报告质量&#xff0c;本文…...

日撸Java三百行(day17:链队列)

目录 一、队列基础知识 1.队列的概念 2.队列的实现 二、代码实现 1.链队列创建 2.链队列遍历 3.入队 4.出队 5.数据测试 6.完整的程序代码 总结 一、队列基础知识 1.队列的概念 今天我们继续学习另一个常见的数据结构——队列。和栈一样&#xff0c;队列也是一种操…...

Android摄像头采集选Camera1还是Camera2?

Camera1还是Camera2&#xff1f; 好多开发者纠结&#xff0c;Android平台采集摄像头&#xff0c;到底是用Camera1还是Camera2&#xff1f;实际上&#xff0c;Camera1和Camera2分别对应相机API1和相机API2。Android 5.0开始&#xff0c;已经弃用了Camera API1&#xff0c;新平台…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...