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

Dijkstra算法C代码

一个带权图n个点m条边,求起点到终点的最短距离

 先定义一个邻接矩阵graph,graph[i][j]表示从i到j的距离,i到j没有路就表示为无穷

然后定义一个visit数组,visit[i]表示i结点是否被访问

然后定义一个dist数组,dist[i]表示起点到i结点的最短距离

第一行输入n和m,表示有n个点m条边

接下来m行输入三个整数a,b,c,表示a到b存在一个距离为c的边

例如输入

4 4
0 1 500
0 2 100
1 3 200
1 2 300

图如下

先初始化dist,初始值为起点到所有点的直达距离

dist={0,500,100,inf},inf表示无穷,即不能直达

一开始起点被访问,所以visit初始化为

visit={1,0,0,0}

将除起点和终点外的每个点都作为中心节点并更新最短路径

一开始dist数组中{0,500,100,inf}最小值为100,对应的点为v2,所以将v2作为中心节点,令mid=2,再计算v2到所有未访问点的直达距离,更新dist,此时还有v1和v3未访问

dist变为{0,400,100,inf}

然后令visit[mid]=1表示已访问,依次类推,经过n-1轮后每个点visit位都为1,这个时候dist数组中dist[i]就表示起点到i结点的最短路径

#include<stdio.h>
#define inf 99999;	//定义99999为无穷大 
int dist[10];
int visit[10];
int graph[10][10];
int main(){scanf("%d%d",&n,&m);//先初始化所有边为无穷 for(i=0;i<n;i++){for(j=0;j<n;j++)graph[i][j]=inf;}//根据输入修改graghfor(i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);	//从a到b的距离为c graph[a][b]=c;graph[b][a]=c;	//由于是无向图,所以反过来也是c graph[i][i]=0;	//自己到自己距离为0}visit[0]=1;	//起点访问初始化为0 for(i=0;i<n;i++)dist[i]=graph[0][i];for(i=1;i<n;i++){//n个点需要n-1轮循环,因为一开始起点已经初始化了 //找dist数组最小值并记录下标为mid min_dist=inf;mid=0; for(j=0;j<n;j++){if((visit[j]==0) && (dist[j]<min_dist)){min_dist=dist[j];mid=j;}}//以mid为中心节点更新dist for(k=0;k<n;k++){if((visit[k]==0) && (dist[k]>dist[mid]+graph[mid][k])){dist[k]=dist[mid]+graph[mid][k];}}visit[mid]=1;//更新完后标记mid为访问 }for(i=0;i<n;i++)printf("%d ",dist[i]);	//输出起点到每个点的最短路径return 0;
}

相关文章:

Dijkstra算法C代码

一个带权图n个点m条边&#xff0c;求起点到终点的最短距离 先定义一个邻接矩阵graph&#xff0c;graph[i][j]表示从i到j的距离&#xff0c;i到j没有路就表示为无穷 然后定义一个visit数组&#xff0c;visit[i]表示i结点是否被访问 然后定义一个dist数组&#xff0c;dist[i]表…...

P1064 [NOIP2006 提高组] 金明的预算方案

[NOIP2006 提高组] 金明的预算方案 题目描述 金明今天很开心&#xff0c;家里购置的新房就要领钥匙了&#xff0c;新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是&#xff0c;妈妈昨天对他说&#xff1a;“你的房间需要购买哪些物品&#xff0c;怎么布置&#xff0…...

大型企业组网如何规划网络

大型企业组网是一个复杂的过程&#xff0c;它需要细致的规划和设计&#xff0c;以确保网络能够满足企业的业务需求&#xff0c;同时保证性能、安全性和可扩展性。以下是规划大型企业网络的一些关键步骤和考虑因素&#xff1a; 1. 需求分析 业务需求&#xff1a;与各个业务部门…...

java:aocache的单实例缓存(二)

之前一篇博客《java:aocache的单实例缓存》介绍了aoocache使用注解AoCacheable实现单实例缓存的方式&#xff0c;同时也指出了这种方式的使用限制&#xff0c;就是这个注解定义的构造方法&#xff0c;不能再创建出新实例。 为了更灵活方便的实现单实例。aocache最新版本0.4.0增…...

ElasticSearch安装部署

简介 Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;用于实时地存储、检索和分析大数据量。它基于 Apache Lucene 搜索引擎库构建而成&#xff0c;提供了一个强大、稳定且易于扩展的搜索解决方案。 主要特点和用途&#xff1a; 分布式存储和搜索&#xff1a; E…...

数据赋能(132)——开发:数据转换——影响因素、直接作用、主要特征

影响因素 数据转换过程中需要考虑的一些影响因素&#xff1a; 数据格式与结构&#xff1a; 不同系统或应用可能使用不同的数据格式&#xff08;如JSON、XML、CSV等&#xff09;和数据结构&#xff08;如关系型数据库、非关系型数据库等&#xff09;。数据转换需要确保原始数据…...

TMGM:ASIC撤销禁令,TMGM强化合规、重启差价合约服务

TMGM作为差价合约&#xff08;CFDs&#xff09;与保证金外汇交易领域的领航者&#xff0c;安全、合规、高效被奉为我集团的终身使命。澳大利亚证券和投资委员会&#xff08;ASIC&#xff09;已正式撤销了早前针对TMGM差价合约业务实施的临时止损令。这一误会的解除&#xff0c;…...

基于SpringBoot网吧管理系统设计和实现(源码+LW+调试文档+讲解等)

&#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者&#xff0c;博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; Java精品实战案例《600套》 2025-2026年最值得选择的Java毕业设计选题大全&#xff1…...

实测2024年最佳的三款Socks5代理IP网站

一、引言 在浩瀚的网络世界中&#xff0c;Socks5代理IP服务如同导航灯塔&#xff0c;指引我们穿越数据海洋&#xff0c;安全、稳定地访问目标网站。作为专业的测评团队&#xff0c;我们深知一款优秀的Socks5代理IP网站需要具备哪些特质&#xff1a;稳定的IP资源、高效的连接速…...

Pythonnet能导入clr,但无法引入System模块?

【pythonnet详解】—— Python 和 .NET 互操作的库_pythonnet 详细使用-CSDN博客 Python中动态调用C#的dll动态链接库中方法_python 如何调用c# dll-CSDN博客 需求&#xff1a;Python调用并传List<float>类型参数给.Net 起初&#xff1a;直接 # 创建一个Python浮点数…...

媒体宣发套餐的概述及推广方法-华媒舍

在今天的数字化时代&#xff0c;对于产品和服务的宣传已经变得不可或缺。媒体宣发套餐作为一种高效的宣传方式&#xff0c;在帮助企业塑造品牌形象、扩大影响力方面扮演着重要角色。本文将揭秘媒体宣发套餐&#xff0c;为您呈现一条通往成功的路。 1. 媒体宣发套餐的概述 媒体…...

Windows和Linux C++判断磁盘空间是否充足

基本是由百度Ai写代码生成的&#xff0c;记录一下。实现此功能需要调用系统的API函数。 对于Windows&#xff0c;可调用函数GetDiskFreeSpaceEx&#xff0c;使用该函数需要包含头文件windows.h。该函数的原型&#xff1a; 它的四个参数&#xff1a; lpDirectoryName&#xff0…...

数据访问层如何提取数据到其他层,其他类中

当然可以&#xff0c;以下是一些具体的例子&#xff0c;展示了如何将数据库访问逻辑封装在一个单独的类中&#xff0c;并在其他类中使用这个类来获取数据。 数据库访问类&#xff08;DatabaseAccess.java&#xff09;&#xff1a; java复制代码 import java.sql.*; import ja…...

【JS】AI总结:JavaScript中常用的判空方法

在JavaScript中&#xff0c;判空是一个常见的操作&#xff0c;因为变量可能未定义、未初始化或包含特定的空值。以下是JavaScript中常用的判空方法&#xff1a; 使用if语句直接判断&#xff1a; 如果变量是null、undefined、0、NaN、空字符串&#xff08;""&#xff…...

Rust单元测试、集成测试

单元测试、集成测试 在了解了如何在 Rust 中写测试用例后&#xff0c;本章节我们将学习如何实现单元测试、集成测试&#xff0c;其实它们用到的技术还是上一章节中的测试技术&#xff0c;只不过对如何组织测试代码提出了新的要求。 单元测试 单元测试目标是测试某一个代码单…...

vue全局方法plugins/utils

一、在src目录下创建一个plugins文件夹 test.ts文件存放创建的方法&#xff0c;index.ts用于接收所有自定义方法进行统一处理 二、编写自定义方法 // test.ts文件 export default {handleTest(val1: number, val2: number) {// 只是一个求和的方法return val1 val2;}, };三…...

高阶算法班从入门到精通之路

课程介绍 本课程旨在帮助学员深入理解算法与数据结构的核心概念&#xff0c;从而掌握高级算法设计与分析技能。每集课程内容精心设计&#xff0c;涵盖了常用数据结构、经典算法及其应用场景等方面的深度讲解&#xff0c;同时通过大量实例演练&#xff0c;帮助学员提升解决实际…...

C++ 左值右值

文章目录 概述左值右值右值引用左值和右值的互换 小结 概述 左值和右值属于2中不同的表达式类型&#xff1b;它们在表达式中扮演不同的角色&#xff0c;特别是在赋值操作和函数参数传递中。 左值 定义&#xff1a;左值是指那些在内存中有确定位置的表达式&#xff0c;可以出…...

[数据集][目标检测]水面垃圾水面漂浮物检测数据集VOC+YOLO格式3749张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;3749 标注数量(xml文件个数)&#xff1a;3749 标注数量(txt文件个数)&#xff1a;3749 标注…...

[深度学习] 卷积神经网络CNN

卷积神经网络&#xff08;Convolutional Neural Network, CNN&#xff09;是一种专门用于处理数据具有类似网格结构的神经网络&#xff0c;最常用于图像数据处理。 一、CNN的详细过程&#xff1a; 1. 输入层 输入层接收原始数据&#xff0c;例如一张图像&#xff0c;它可以被…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...