最短路,dijsktra 算法,HDU-2544

标签: dijsktra  HDU-2544  最短路

从最开始认识算法,到现在被吸引,这种感觉有点其妙。开始我认为算法就是简单的数学问题,到现在我认为算法真的是一种思想,一种逻辑思维让我们的大脑更加的清楚认识到这个问题的答案,从开始到最后的一步步推理,一步步接近正确答案的兴奋,这种兴奋,让我对算法着迷。LOVE 算法。LOVE计算机。

好吧不发牢骚了,让我们一起去深入了解一下如何求最短路径。有了这种思想(算法思想),我觉得真的很神奇。

给你好多好多个岛,然后他们某两个岛之间有路(路何以重复)然后让把你放到其中一个岛上,让你向另一个岛逃亡,

这个问题的本质就是,让你从起点岛到终点岛,找到一个最短的路径。

现在我们来举一个例子,这个是个无向图。

看到这个图了吧,下面他会让你找1岛到任何一个岛的距离最小值。

我们用一个数组来存这个距离

第一次我们先把1岛当作基本的开始对连着1岛的所有岛遍历(更新路径)就是所有和1岛相连的,不相连的距离先假设为无穷大

.然后在这6个距离中找到最小的dis[2]也就是10,标记一下(标记一下下次再次更新的时候不需要更新这个岛,因为这个距离已经是这个岛到1岛的最短路径了),然后更新和2岛相连的岛如果距离小于目前距离则更新(就是我用红色圈起来的),也就是1-2-3的距离从无穷大到60,

之后继续找这个数组里没有被标记过的最小值,30,标记一下更新与4岛相连的岛到1岛的距离,1岛到3岛由1-2-3到1-4-3距离由60变成50,1岛到5岛由1-5变为1-4-5距离由100到90.

然后继续找最小没有被标记过的,50,标记一下,更新一下跟3岛相连距离1岛有没有变近的,发现5岛变近了从90变到了60,路径由1-4-5到1-2-3-5.

继续按这个原则更新直到最后全部点都更新完成。我们就找到了所有岛到1岛的最短路径

,hello,hello,~~~~我讲清楚了没呢,下面让我给大家再来个图试试手

 

答案就是

我们下来看一个例题

HDU-2544:http://acm.hdu.edu.cn/showproblem.php?pid=2544

题目的意思就是从1到n的距离最短是多少。

上代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=155;
int n,m;
int mp[MAXN][MAXN],dis[MAXN];//mp是为了存邻接矩阵,dis标记到1最短距离
bool vis[MAXN];//标记是否遍历过
void init(){//初始化
	memset(vis,0,sizeof(vis));
	memset(dis,0,sizeof(dis));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++){
			if(i==j) mp[i][j]=0;
			else mp[i][j]=INF;
		}
	}
}
void dijkstra(){
	int minn,k=-1;
	for(int i=1;i<=n;i++)
	dis[i]=mp[1][i];
	dis[1]=0;
	vis[1]=1;
	for(int i=1;i<=n;i++)//从1遍历到n
	{
		minn=INF; 
		for(int j=1;j<=n;j++)//每次找到距离1最近且没有被标记的点
		{
			if(dis[j]<minn&&!vis[j])
			{
				minn=dis[j];
				k=j;
			}
		}
		vis[k]=1;//标记一下
		for(int j=1;j<=n;j++)//松弛
            if(!vis[j])//如果没有被标记且距离变小,就松弛一下
            dis[j]=min(dis[j],dis[k]+mp[k][j]);//两个数的最小值
	}
	cout<<dis[n]<< endl;
}
int main(){
	while(scanf("%d%d",&n,&m)&& n+m)
	{
		init();
		int a,b,c;
		for(int i=1;i<=m;i++)//存图
		{
			cin>>a>>b>>c;
			if(mp[a][b]>c){
				mp[a][b]=c;
				mp[b][a]=c;
			}
		}
		dijkstra();
	}
	return 0;
}

 

版权声明:本文为Harington原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Harington/article/details/81974272

智能推荐

Valine-1.4.4新版本尝鲜+个性制定(表情包、qq头像、UI样式)

文章目录 一、前言 二、尝鲜 三、个性定制 1. 大佬版 2.“傻瓜”版 3.平民版 (1)自定义背景 (2)增添个性表情 (3) 根据邮箱拉取qq头像 (4)diy魔改样式 一、前言 大晚上又魔改评论系统了, 2020年4月16日01:56:39把新版本的自定义图片改出来了,2333,valine的新版本变化蛮大的。 二、尝鲜 1.4.4 强势来袭,尝鲜加体验。 文末给出...

RxJava源码分析(2) 变换原理

RxJava源码分析基于RxJava1.3.8。 在上一章节中,主要介绍了RxJava的基本使用并对该部分的源码做了详细分析。在这一章节中,将主要介绍RxJava的另一大核心功能:变换。 变换,就是将事件序列中的对象或整个序列进行加工处理,转换成不同的事件或事件序列。 在RxJava中,提供了许多针对不同场景实现变换功能的操作符,如下: map() flatMap(), concatMap(), ...

CVE-2017-11176: A step-by-step Linux Kernel exploitation (part 4/4)

CVE-2017-11176: A step-by-step Linux Kernel exploitation (part 3/4) 本文的原文地址:https://blog.lexfo.fr/cve-2017-11176-linux-kernel-exploitation-part4.html 介绍 在最后的这个部分中,我们将会把任意调用转换成在ring0权限下的任意代码执行,修复内核拿到ro...

一道简单的Docker题

docker是什么? 我觉得大致可以理解为linux环境下的虚拟机(容器) 就跟windows环境下的vmware一样 在打中科大hackergame2020的时候发现有一道docker题 先复习下docker的相关命令: 这里! 然后开始做题 首先先配置好本地的docker环境,apt-get换成浙大源(经过测试这个源下载安装docker速度超快,吊打阿里清华源) 然后安装 docker 首先需...

企业权限管理系统---产品管理

查询所有产品 添加产品 具体实现: jsp页面内容: Cntroller层代码 service层 dao层...

猜你喜欢

拒绝无用功,封装一个通用的PopupWindow

作者: 夏至,欢迎转载,但请保留这段申明,谢谢 https://juejin.im/post/5961e03e51882568b13c3308 为了避免重复造轮子,我们一般都会封装一个通用的控件,比如这次,项目中需要用到比较多的 popupwindow ,如果需要一个个写,那么依旧会累死人,而且还是无用功,无意义,所以,封装一个通用的,除了让同事看了直刷666之外,自己还省了很多事情。 先上效果图...

【数据库】关系数据库(Relational Databases)

关系数据库(Relational Databases) 关系数据库,是建立在关系数据库模型基础上的数据库,借助于集合代数等概念和方法来处理数据库中的数据 Relational Query Languages Tuple Relational Calculus (TRC) Relational Algebra (RA) SQL 举例说明: 零、名词概念 1. 基数 和 参数数 cardinality...

zabbix多台监控-proxy分布式监控

zabbix:proxy分布式监控 server3:zabbix-proxy 1、安装 2、开启mysql 3、编写配置文件 4、网页配置添加代理 server1:zabbix-server server2:zabbix-agent...

Collection

Collection 中的方法,全部来自API,读者无需硬性记忆,只需牢记:集合类就像容器,显示生活中容器的功能,也就是添加对象、删除对象、清空容器、判断容器是否为空等,集合类就为这些功能提供了对应的方法。 Collection基本方法: 输出结果: 转自:https://blog.csdn.net/wxc880924/article/details/52639701...

hive on spark部署

1. 环境 Hive-on-MR is deprecated in Hive 2 and may not be available in the future versions. Consider using a different execution engine (i.e. tez, spark) or using Hive 1.X releases. hive默认使用mr作为计算引擎,当进入...