单源最短路径:Dijkstra算法(堆优化)

栏目: IT技术 · 发布时间: 4年前

内容简介:前言:趁着对Dijkstra还有点印象,赶快写一篇笔记。注意:本文章面向已有Dijkstra算法基础的童鞋。单源最短路径,在我的理解里就是求从一个源点(起点)到其它点的最短路径的长度。

前言:趁着对Dijkstra还有点印象,赶快写一篇笔记。

注意:本文章面向已有Dijkstra算法基础的童鞋。

简介

单源最短路径,在我的理解里就是求从一个源点(起点)到其它点的最短路径的长度。

当然,也可以输出这条路径,都不是难事。

但是,Dijkstra不能处理有负权边的图。

解析

注:接下来,我们的源点均默认为1。

先上代码( 注意,是堆优化过的!! ):

struct node{
	int id;
	int total;
	node(){};
	node(int Id,int Total){
		id=Id;
		total=Total;
	}
	bool operator < (const node& x) const{
		return total>x.total;
	}
};

void dijkstra(int start){
	memset(dis,inf,sizeof(dis));
	memset(conf,false,sizeof(conf));
	memset(pre,0,sizeof(pre));
	dis[start]=0;
	priority_queue <node> Q;
	Q.push(node(1,0));
	while(Q.size()){
		int u=Q.top().id;
		Q.pop();
		if(conf[u])
		continue;
		conf[u]=true;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			int cost=dis[u]+e[i].w;
			if(cost < dis[v]){
				dis[v]=cost;
				pre[v]=u;
				Q.push(node(v,dis[v]));
			}
		}
	}
}

接下来,一步一步解析代码:

首先是结构体 node

struct node{
	int id;
	int total;
	node(){};
	node(int Id,int Total){
		id=Id;
		total=Total;
	}
	bool operator < (const node& x) const{
		return total>x.total;
	}
};

这里的id就是这个结点的编号,total就是走到当前节点的最小花费。

构造函数就不用我多说了吧。

因为在原始的Dijkstra中,每次都要选出当前花费最小的那个点,如果采用堆优化,使得堆头永远都是花费最小的那个,这样每次选出花费最小的那个点的时间复杂度从 \(O(n)\) 骤降到 \(O(logn)\)

如果要用到堆,就可以使用STL的优先队列( priority_queue )。

因为优先队列默认是优先级最高的放在最前面,在Dijkstra中,优先级就是这个node的total,total越小优先级就越高。

因为total越大,优先级越低,所以这里的小于运算符就可以定义为 total>x.total

接下来是初始化

memset(dis,inf,sizeof(dis));
memset(conf,false,sizeof(conf));
memset(pre,0,sizeof(pre));
dis[start]=0;
Q.push(node(1,0));

数组 dis[i] 表示的是从源点到点i的最短路的长度,初始时不知道能不能到达,设为 inf (无穷大)。

数组 conf[i] 表示的是点i的最短路径是否确认,若是,则为 true ,否则为 false

数组 pre[i] 表示的是点i的前驱,即到点i的前一个点的编号。

例如有一条最短路径是这样的: 1->3->8->5->2 ,那么 pre[2]=5;pre[5]=8;pre[8]=3;

这样一来,输出路径就好办了:

//假设要输出到2的路径
int i=2;
while(pre[i]!=1){
	ans.push(i);
	i=pre[i];
}
printf("1");
while(!ans.empty()){
	printf("->%d",ans.top());
	ans.pop();
}

此外,一开始从结点1出发,到结点1的距离为0,知道这些信息后,将源点入堆。

Q.push(node(1/*节点编号*/,0/*到该节点距离*/));

接下来是重点了,我们再次一步步地拆分:

int u=Q.top().id;
Q.pop();
if(conf[u])
continue;
conf[u]=true;

这个应该不难理解,首先拿出一个源点u,u的编号自然是 Q.top().id 。接下来 Q.pop() 必不可少。

这时候,如果 conf[u]==true ,即结点u的最短路长度已经确定过了,那就没必要再走了,因为之前肯定走过了。直接 continue 看下一个结点。

如果没有,按照Dijkstra的特性,当前结点u的总路径长度肯定是最短了,那么就被确定了, conf[u]=true

然后是下一段:

for(int i=head[u];i;i=e[i].nxt){
	int v=e[i].v;
	int cost=dis[u]+e[i].w;
	if(cost < dis[v]){
		dis[v]=cost;
		pre[v]=u;
		Q.push(node(v,dis[v]));
	}
}

这段其实好理解,不过我用的是链式前向星存图,如果你用的是vector做的邻接表,其实大体上是相同的。

如果你用的是邻接表或邻接矩阵,这里的 v 其实就是当前找的这条路的终点( e[i].v 表示的是这条边的终点。

cost ,则是 dis[u] 的值加上这条边的权值(没错, e[i].w 表示的是这条边的权值),也就是到点v的总花费。

如果 cost<dis[v] ,即当前这条路到v的总花费比原来到v的总花费小,就可以更新了:

dis[v]=cost;
pre[v]=u;
Q.push(node(v,dis[v]));

首先是总花费更新,然后再更新前驱,最后把这个到过的点放入优先队列里。

至此,堆优化Dijkstra就结束了。

但是有一个比较关心的点:时间复杂度是多少呢?

首先考虑有哪些结点会被搜索:

显然是一开始 conf[u]==false 的结点,而一点出堆之后, conf[u]=true ,所以有 n 个节点会被搜索同时入队,每次入队需要 \(O(logn)\)

接下来是遍历每个结点的边,如果用 \(E_i\) 表示和结点 \(i\) 相邻的边的数量,显然有: \(\sum_{i=1}^n E_i = m\) ,在最坏情况下,每次搜索边的时候都要入队一次,那么总时间复杂度就是: \(O(mlogn)\)

完结撒花✿

未经博主允许禁止转载!


以上所述就是小编给大家介绍的《单源最短路径:Dijkstra算法(堆优化)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

交易系统

交易系统

武剑锋 / 上海人民出版社 / 2011-1 / 32.00元

《交易系统:更新与跨越》是中国第一部研究证券交易系统的专业著作,填补了这一领域的学术空白。既回顾和总结了系统规划、建设和上线过程中,技术管理、架构设计、应用调优、切换部署、运行维护等方面的经验和教训,也从较为宏观的角度描述了独具中国特色的交易技术支撑体系,特别是,通过分析其他资本市场交易系统的近年来发展历程和后续的技术发展规划,探索了未来业务创新和技术创新的大致框架和可能的模式。相信《交易系统:更......一起来看看 《交易系统》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具