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条边,求起点到终点的最短距离 先定义一个邻接矩阵graph,graph[i][j]表示从i到j的距离,i到j没有路就表示为无穷 然后定义一个visit数组,visit[i]表示i结点是否被访问 然后定义一个dist数组,dist[i]表…...
P1064 [NOIP2006 提高组] 金明的预算方案
[NOIP2006 提高组] 金明的预算方案 题目描述 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置࿰…...
大型企业组网如何规划网络
大型企业组网是一个复杂的过程,它需要细致的规划和设计,以确保网络能够满足企业的业务需求,同时保证性能、安全性和可扩展性。以下是规划大型企业网络的一些关键步骤和考虑因素: 1. 需求分析 业务需求:与各个业务部门…...
java:aocache的单实例缓存(二)
之前一篇博客《java:aocache的单实例缓存》介绍了aoocache使用注解AoCacheable实现单实例缓存的方式,同时也指出了这种方式的使用限制,就是这个注解定义的构造方法,不能再创建出新实例。 为了更灵活方便的实现单实例。aocache最新版本0.4.0增…...
ElasticSearch安装部署
简介 Elasticsearch 是一个开源的分布式搜索和分析引擎,用于实时地存储、检索和分析大数据量。它基于 Apache Lucene 搜索引擎库构建而成,提供了一个强大、稳定且易于扩展的搜索解决方案。 主要特点和用途: 分布式存储和搜索: E…...
数据赋能(132)——开发:数据转换——影响因素、直接作用、主要特征
影响因素 数据转换过程中需要考虑的一些影响因素: 数据格式与结构: 不同系统或应用可能使用不同的数据格式(如JSON、XML、CSV等)和数据结构(如关系型数据库、非关系型数据库等)。数据转换需要确保原始数据…...
TMGM:ASIC撤销禁令,TMGM强化合规、重启差价合约服务
TMGM作为差价合约(CFDs)与保证金外汇交易领域的领航者,安全、合规、高效被奉为我集团的终身使命。澳大利亚证券和投资委员会(ASIC)已正式撤销了早前针对TMGM差价合约业务实施的临时止损令。这一误会的解除,…...
基于SpringBoot网吧管理系统设计和实现(源码+LW+调试文档+讲解等)
💗博主介绍:✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者,博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌💗 Java精品实战案例《600套》 2025-2026年最值得选择的Java毕业设计选题大全࿱…...
实测2024年最佳的三款Socks5代理IP网站
一、引言 在浩瀚的网络世界中,Socks5代理IP服务如同导航灯塔,指引我们穿越数据海洋,安全、稳定地访问目标网站。作为专业的测评团队,我们深知一款优秀的Socks5代理IP网站需要具备哪些特质:稳定的IP资源、高效的连接速…...
Pythonnet能导入clr,但无法引入System模块?
【pythonnet详解】—— Python 和 .NET 互操作的库_pythonnet 详细使用-CSDN博客 Python中动态调用C#的dll动态链接库中方法_python 如何调用c# dll-CSDN博客 需求:Python调用并传List<float>类型参数给.Net 起初:直接 # 创建一个Python浮点数…...
媒体宣发套餐的概述及推广方法-华媒舍
在今天的数字化时代,对于产品和服务的宣传已经变得不可或缺。媒体宣发套餐作为一种高效的宣传方式,在帮助企业塑造品牌形象、扩大影响力方面扮演着重要角色。本文将揭秘媒体宣发套餐,为您呈现一条通往成功的路。 1. 媒体宣发套餐的概述 媒体…...
Windows和Linux C++判断磁盘空间是否充足
基本是由百度Ai写代码生成的,记录一下。实现此功能需要调用系统的API函数。 对于Windows,可调用函数GetDiskFreeSpaceEx,使用该函数需要包含头文件windows.h。该函数的原型: 它的四个参数: lpDirectoryName࿰…...
数据访问层如何提取数据到其他层,其他类中
当然可以,以下是一些具体的例子,展示了如何将数据库访问逻辑封装在一个单独的类中,并在其他类中使用这个类来获取数据。 数据库访问类(DatabaseAccess.java): java复制代码 import java.sql.*; import ja…...
【JS】AI总结:JavaScript中常用的判空方法
在JavaScript中,判空是一个常见的操作,因为变量可能未定义、未初始化或包含特定的空值。以下是JavaScript中常用的判空方法: 使用if语句直接判断: 如果变量是null、undefined、0、NaN、空字符串(""ÿ…...
Rust单元测试、集成测试
单元测试、集成测试 在了解了如何在 Rust 中写测试用例后,本章节我们将学习如何实现单元测试、集成测试,其实它们用到的技术还是上一章节中的测试技术,只不过对如何组织测试代码提出了新的要求。 单元测试 单元测试目标是测试某一个代码单…...
vue全局方法plugins/utils
一、在src目录下创建一个plugins文件夹 test.ts文件存放创建的方法,index.ts用于接收所有自定义方法进行统一处理 二、编写自定义方法 // test.ts文件 export default {handleTest(val1: number, val2: number) {// 只是一个求和的方法return val1 val2;}, };三…...
高阶算法班从入门到精通之路
课程介绍 本课程旨在帮助学员深入理解算法与数据结构的核心概念,从而掌握高级算法设计与分析技能。每集课程内容精心设计,涵盖了常用数据结构、经典算法及其应用场景等方面的深度讲解,同时通过大量实例演练,帮助学员提升解决实际…...
C++ 左值右值
文章目录 概述左值右值右值引用左值和右值的互换 小结 概述 左值和右值属于2中不同的表达式类型;它们在表达式中扮演不同的角色,特别是在赋值操作和函数参数传递中。 左值 定义:左值是指那些在内存中有确定位置的表达式,可以出…...
[数据集][目标检测]水面垃圾水面漂浮物检测数据集VOC+YOLO格式3749张1类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):3749 标注数量(xml文件个数):3749 标注数量(txt文件个数):3749 标注…...
[深度学习] 卷积神经网络CNN
卷积神经网络(Convolutional Neural Network, CNN)是一种专门用于处理数据具有类似网格结构的神经网络,最常用于图像数据处理。 一、CNN的详细过程: 1. 输入层 输入层接收原始数据,例如一张图像,它可以被…...
保姆级教程:用串口和Telnet连接Hi3559/Hi3516开发板,5分钟搞定环境搭建
5分钟极速上手:Hi3559/Hi3516开发板串口与Telnet连接实战指南 刚拿到海思开发板时,许多开发者会被一堆陌生的接口和术语吓退。其实只要掌握几个关键步骤,从拆箱到建立稳定连接只需一根串口线和五分钟时间。本文将用最直白的语言,带…...
22:L应用区块链+AI:蓝队的分布式安全
作者: HOS(安全风信子) 日期: 2026-03-19 主要来源平台: GitHub 摘要: 区块链的不可篡改特性与AI的智能分析能力相结合,为蓝队防御带来了新的可能性。L深入研究区块链AI的融合应用,构建了一个分布式、透明、…...
Gemma-3-12b-it实战教程:对接企业微信/钉钉机器人实现图文消息自动解析
Gemma-3-12b-it实战教程:对接企业微信/钉钉机器人实现图文消息自动解析 1. 引言:当多模态AI遇上企业协作 想象一下这个场景:你的同事在企业微信群里发了一张复杂的业务流程图,问“这个流程的第三步有什么风险?”或者…...
Wan2.2-I2V-A14B开源可部署:符合等保2.0要求,支持审计日志+访问控制
Wan2.2-I2V-A14B开源可部署:符合等保2.0要求,支持审计日志访问控制 1. 镜像概述与核心特性 Wan2.2-I2V-A14B是一款专为文生视频任务优化的私有部署镜像,基于RTX 4090D 24GB显存显卡和CUDA 12.4环境深度定制。本镜像不仅提供高性能的视频生成…...
MATLAB 数值计算辅助:分析 Stable Yogi 生成图像的色彩与纹理特征
MATLAB 数值计算辅助:分析 Stable Yogi 生成图像的色彩与纹理特征 1. 引言 最近在尝试用 Stable Yogi 生成一些皮革纹理的设计图,效果确实挺惊艳的。但生成得多了,就遇到一个新问题:我手头攒了几百张图,风格各异&…...
Charticulator:颠覆式图表构建引擎如何让数据工作者实现零代码可视化创新
Charticulator:颠覆式图表构建引擎如何让数据工作者实现零代码可视化创新 【免费下载链接】charticulator Interactive Layout-Aware Construction of Bespoke Charts 项目地址: https://gitcode.com/gh_mirrors/ch/charticulator 数据可视化领域长期面临着模…...
3个关键步骤:Smiley Sans字体技术优化指南
3个关键步骤:Smiley Sans字体技术优化指南 【免费下载链接】smiley-sans 得意黑 Smiley Sans:一款在人文观感和几何特征中寻找平衡的中文黑体 项目地址: https://gitcode.com/gh_mirrors/smi/smiley-sans 在当今数字化时代,网页性能直…...
零售店长必看:如何用iBeacon+微信小程序打造低成本智能导购(2024最新方案)
零售店长必看:如何用iBeacon微信小程序打造低成本智能导购(2024最新方案) 走进任何一家现代零售门店,你可能会注意到顾客们不再茫然地寻找商品,而是自然地掏出手机,接收个性化的商品推荐和促销信息。这种无…...
GIL已死,GIL万岁?——2024大厂Python并发岗面试题库首发(含性能压测对比数据)
第一章:GIL已死,GIL万岁?——2024大厂Python并发岗面试题库首发(含性能压测对比数据)一道高频真题:为什么 asyncio.run() 启动的协程无法被 multiprocessing.Process 并发执行? 该问题直指 Pyth…...
个人开发者如何高效率APP上架安卓应用市场?软著、备案、资质、审核详解大全,一篇文章讲透流程规则!
一、上架前的资质准备 1. 软件著作权登记证书(软著) 软著是证明APP拥有自主知识产权的重要文件,多数应用商店要求上架时提供。申请周期通常为1-2个月,建议提前规划。 2. APP备案 根据工信部要求,APP主办者需要在接…...
