(算法基础)朴素版的Dijkstra算法

news/2024/4/15 8:07:50

适用情景

  1. 在最短路问题当中的单源最短路(一号点到其他所有点之间的距离)的只有正权边的情况。


时间复杂度

  1. O(N^2)


算法解释(朴素版的Dijkstra)

  1. 首先是关于这个图的存储,图的话主要是分为稠密图与稀疏图。稠密图就是说n的平方与m是一个量级的,对于稠密图的话,用邻接矩阵来存;稀疏图的话是n与m为一个量级的,对与稀疏图的话,就用邻接表来存。在这边我先举一个用邻接矩阵存图为例子吧。

int g[N][N];
  1. 然后这个邻接矩阵等会儿我是要把具体的边的信息放进去的,所以在一开始有必要进行一些预处理初始化,在最短路问题当中有两类特殊情况:这就是重边,一个就是自环,由于当下背景是最短路,对于重边而言的话,只需要取小的就可以;然后对于自环而言的话,不能是负环(不然最短路就变成负无穷了),然后对于正环而言的话,在最短路里相当于没有,所以就这样初始化

for (int i=1;i<=n;i++)
{for (int j=1;j<=n;j++){if (i==j){g[i][j]=0;}else{g[i][j]=0x3f3f3f3f;  //为等会儿输入边权重取小做准备}}
}
  1. 然后还需要开两个数组,一个数组就是用来记录一下该点是不是已经确定了最短路距离,还有一个数组用来记录一下每点到一号点之间的最短路距离是多少,一开始的话每点初始化为正无穷(当然,一号点除外,它到他自己本身的距离就是0

int st[N];
int dist[N];
memset(dist,0x3f3f3f3f,sizeof(dist));
dist[1]=0;
  1. 然后往邻接矩阵里面输入每一条边的有关信息.

while(m--)
{int a,b,c;scanf("%d %d %d",&a,&b,&c);g[a][b]=MIN(g[a][b],c);
}
  1. 然后就进入了迪杰斯特拉算法的精髓:首先要去找到这么一个点1. 还没有被正式确认下来最短路距离,2. 到1号点的距离比其他与他一样的同胞(还没有被正式确认最短路距离)到一号点的距离都要短(因此逃不开还要遍历一遍所有点)。先把这个点去找到,这个点找到之后,去遍历一下这个点所能连接到的其他点,看一看能不能更新那些点的最短路距离。遍历一圈完成之后,这个点的最短路距离也就正式被确定下来然后依次往复,不断循环。显而易见,每一次循环确定下来一个点的最短路距离,既然有n个点,那么就需要n次循环

for (int i=0;i<n;i++)
{int t=0;for (int j=1;j<=n;j++){if (st[j]==0 && (t==0 || dist[j]<dist[t])){t=j;}}st[t]=1;for (int j=1;j<=n;j++){dist[j]=MIN(dist[j],dist[t]+g[t][j]);}
}
  1. 然后由于迪杰斯特拉算法的要求,就是说所有的边都必须是正权边,因此如果说从一号点走不到n号点的话,那么n号点的距离dist应该还是保持初始化的那个值0x3f3f3f3f,在当前情形是不存在负权边,这个初始化的正无穷大值不会被略微更新小

if (dist[n]==0x3f3f3f3f)
{printf("%d\n",-1);
}
else
{printf("%d\n",dist[n]);
}

例题

来源:AcWing

849. Dijkstra求最短路 I - AcWing题库

#include <stdio.h>
#include <string.h>
#define N 510
#define MIN(a,b) ((a)<(b)?(a):(b))
int g[N][N];
int st[N];
int dist[N];
int main()
{memset(dist,0x3f3f3f3f,sizeof(dist));dist[1]=0;int n,m;scanf("%d %d",&n,&m);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (i==j){g[i][j]=0;}else{g[i][j]=0x3f3f3f3f;  //为等会儿输入边权重取小做准备}}}while(m--){int a,b,c;scanf("%d %d %d",&a,&b,&c);g[a][b]=MIN(g[a][b],c);}for (int i=0;i<n;i++){int t=0;for (int j=1;j<=n;j++){if (st[j]==0 && (t==0 || dist[j]<dist[t])){t=j;}}st[t]=1;for (int j=1;j<=n;j++){dist[j]=MIN(dist[j],dist[t]+g[t][j]);}}if (dist[n]==0x3f3f3f3f){printf("%d\n",-1);}else{printf("%d\n",dist[n]);}return 0;
}

http://www.ppmy.cn/news/35153.html

相关文章

C++分析以下关于指针的操作有什么问题

代码一:按值传递/按引用传递 按值传递是指,在函数调用时,将参数的值复制一份传递给函数,函数中对参数值的修改不会影响到原始值 对于指针类型的参数,在按值传递的情况下,传递给函数的是指针变量的值(即指针变量所存储的地址),而不是指针所指向的内存地址。因此,当在…

一文看懂数据仓库

数据仓库数据仓库的概念数据仓库的主要特征数据仓库的分层数据仓库的分层介绍原始数据层&#xff1a;ODS&#xff08;Operational Data Store&#xff09;数据仓库层&#xff1a;DW&#xff08;Data Warehouse&#xff09;数据明细层&#xff1a;DWD&#xff08;Data Warehouse…

进阶C语言——字符函数和字符串函数【详解】(二)

文章目录1. strtok2. strerror3. memcpy4. memmove5. memcmp6. memset1. strtok sep参数是个字符串&#xff0c;定义了用作分隔符的字符集合第一个参数指定一个字符串&#xff0c;它包含了0个或者多个由sep字符串中一个或者多个分隔符分割的标记strtok函数找到str中的下一个标记…

算法训练:贪心与回溯

目录 1.手套&#xff08;贪心算法&#xff09; 2.字符串通配符&#xff08;回溯算法&#xff09; 1.手套 题目描述&#xff1a; 在地下室里放着n种颜色的手套&#xff0c;手套分左右手&#xff0c;但是每种颜色的左右手手套个数不一定相同。A先生现在要出门&#xff0c;所以…

【redis】redis缓存更新策略

目录一、缓存更新策略二、主动更新策略三、Cache Aside Pattern3.1 删除缓存还是更新缓存?3.2 如何保证缓存与数据库的操作同时成功或失败&#xff1f;3.3 先操作缓存还是先操作数据库3.3.1 先删缓存再删库3.3.2 先删库再删缓存一、缓存更新策略 1.内存淘汰&#xff1a;不用自…

Flutter-Scaffold组件

在Flutter开发当中&#xff0c;我们可能会遇到以下的需求&#xff1a;实现页面组合使用&#xff0c;比如说有悬浮按钮、顶部菜单栏、左右抽屉侧边栏、底部导航栏等等效果。Scaffold组件可以帮我们实现上面需求说的效果。这篇博客主要分享容器组件的Scaffold组件的使用&#xff…

【数据结构篇C++实现】- 堆

文章目录&#x1f680;一、堆的原理精讲⛳&#xff08;一&#xff09;堆的概念⛳&#xff08;二&#xff09;看图识最大堆⛳&#xff08;三&#xff09;详解堆是用数组表示的树&#x1f680;二、堆的向下调整算法&#x1f680;三、堆的向上调整算法&#x1f680;四、将任意一棵…

古茗科技面试:为什么 ElasticSearch 更适合复杂条件搜索?

文章目录 ElasticSearch 简介倒排索引联合索引查询跳表合并策略Bitset 合并策略MySQL 最多使用一个条件涉及的索引来过滤,然后剩余的条件只能在遍历行过程中进行内存过滤。 上述这种处理复杂条件查询的方式因为只能通过一个索引进行过滤,所以需要进行大量的 I/O 操作来读取行…

STM32-9 STM32CubeMX的使用方法

一、 说明 本项目是基于FreeRTOS项目的STM32CubeMX开发方式&#xff0c;说明了具体配置与相关参数&#xff0c;以及mdk使用&#xff0c;裸机也可以参考本配置。 二、项目建立步骤 1、新建项目 2、选择芯片型号 3、配置时钟 RCC 设置&#xff0c;选择 HSE(外部高速时钟) 和L…

【C#学习记录】如何让界面控件实现自适应布局(Winform)

小伙伴们大家好,我是雷工! 在软件界面设计中,客户常常要求设计的界面可以随意缩放,缩放过程中,界面中的按钮等控件也会随着窗体变大缩小自动调整显示位置和尺寸大小。在C#的Winform窗体中如何实现这个效果,下面我们一起学习下。 一、样例开发环境 本样例的程序运行环境…

软件测试学习书籍【附电子版】

零基础学软件测试需要读哪些书籍?软件测试经典书籍推荐什么?对于学习软件测试而言&#xff0c;取得一本好书做指导&#xff0c;那是相当的有价值&#xff0c;好书相当于一位好老师&#xff0c;带你入门&#xff0c;带你走进知识深处&#xff0c;下面小编就给大家推荐一些软件…

MySQL-事务

目录 &#x1f341;什么是事务 &#x1f341;隔离级别 &#x1f343;未提交读 &#x1f343;已提交读 &#x1f343;可重复读 &#x1f343;可串行化 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &#x1f990;MySQL专栏&#xff1a;MySQL专栏地址 什么是事务 多条sql语…

【Python入门第三十八天】Python丨NumPy 简介

什么是 NumPy&#xff1f; NumPy 是用于处理数组的 python 库。 它还拥有在线性代数、傅立叶变换和矩阵领域中工作的函数。 NumPy 由 Travis Oliphant 于 2005 年创建。它是一个开源项目&#xff0c;你可以自由使用它。 NumPy 指的是数值 Python&#xff08;Numerical Pyth…

SpringBoot @SpringBootTest 无法启动服务

这几天在看Hikari、Druid连接池。按照网上代码写Junit测试类。当时代码如下: package com.ceaning.crudp.utils;import org.junit.Test; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; impo…

CAN(FD)记录仪在新能源汽车整车控制器(VCU)、电池管理系统(BMS)、电机控制器(MCU)、发动机ECU中的应用,免去出差烦恼

今天介绍CAN(FD)记录仪在新能源汽车整车控制器&#xff08;VCU&#xff09;、电池管理系统&#xff08;BMS&#xff09;、电机控制器&#xff08;MCU&#xff09;、发动机ECU中的应用 第一步&#xff1a;新能源汽车整车控制器&#xff08;VCU&#xff09;先供上电&#xff0c…

什么是分布式软件系统

:什么是分布式软件系统&#xff1f;分布式软件系统是什么意思&#xff1f; 分布式软件系统(Distributed Software Systems)是支持分布式处理的软件系统,是在由通信网络互联的多处理机体系结构上执行任务的系统。它包括分布式操作系统、分布式程序设计语言及其编译(解释)系统、分…

使用chatGPT实现数字自增动画

num-auto-add&#xff1a;数字自增动画 序言 我们经常在一些好的网站上遇到数字自增的动画效果&#xff0c;为用户提供了更加丰富的交互体验&#xff0c;看起来非常酷。 我之前也有写过&#xff0c;为了方便以后使用&#xff0c;打算将它优化&#xff0c;并上传到npm中。 首…

可别再用BeanUtils了(性能拉胯),试试这款转换神器

老铁们是不是经常为写一些实体转换的原始代码感到头疼&#xff0c;尤其是实体字段特别多的时候。有的人会说&#xff0c;我直接使用get/set方法。没错&#xff0c;get/set方法的确可以解决&#xff0c;而且也是性能较高的处理方法&#xff0c;但是大家有没有想过&#xff0c;要…

页面的重排和重绘?

思路&#xff1a; 网页渲染HTML文件到浏览器的过程->定义->如何优化网页渲染HTML文件到浏览器的过程HTML 文件通过HTML解析器解析生成DOM树&#xff1b;CSS文件通过CSS解析器生成CSSOM树&#xff1b;DOM树和CSSOM树生成渲染树&#xff08;render tree&#xff09;&#x…

Linux进程概念—环境变量

Linux进程概念—环境变量1.孤儿进程2.环境变量2.1常见环境变量2.2查看环境变量方法2.3在环境变量中添加2.4和环境变量相关的命令2.5环境变量的组织方式2.6命令行参数&#x1f31f;&#x1f31f;hello&#xff0c;各位读者大大们你们好呀&#x1f31f;&#x1f31f; &#x1f68…
最新文章