前言: 趁着对 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)\).
完结撒花
未经博主允许禁止转载!
来源: https://www.cnblogs.com/lingfunny/p/12822853.html