内容简介:前言:趁着对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算法(堆优化)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法
- 漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条
- HDFS短路读详解
- 动态规划之最短路径和
- 漫画:如何求图的最短路径? | 技术头条
- ArangoDB 3.5:流事务 API、蒙面数据、搜索性能大幅提升、最短路径功能
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。