单源最短路径: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算法(堆优化)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

个体与交互

个体与交互

Ken Howard、Barry Rogers / 贾永娜、张凯峰 / 机械工业出版社华章公司 / 2012-3-20 / 45.00元

对敏捷软件开发的关注重点,通常都集中在“机制”方面,即过程和工具。“敏捷宣言”认为,个体与交互的价值要高于过程和工具,但这一点很容易被遗忘。在敏捷开发中,如果你重新将注意力放在人的方面,将会收获巨大利益。 本书展示了如何解决敏捷团队在实际项目中遭遇的问题。同时,本书也是很有实用价值的敏捷用户指南,其中包含的故事、最佳实践方法、经验以及技巧均可应用到实际项目当中。通过逐步实践,你将学会如何让团......一起来看看 《个体与交互》 这本书的介绍吧!

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

Base64 编码/解码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具