Dijkstra算法的二叉堆优化

时间:2022-09-30 11:04:54

算法原理

每次扩展一个距离最小的点,再更新与其相邻的点的距离。

如何寻找距离最小的点

普通的Dijkstra算法的思路是直接For i: 1 to n

优化方案是建一个小根堆,小根堆里存储由当前结点更新距离的所有点,那么堆顶就是距离最小的点

如何寻找与源点相邻的点

当然是邻接表

具体实现

建一个小根堆heap[] ,用来存储结点的序号,用一个数组pos[i] 来存储第i个结点在堆中的位置,用一个标记数组in_heap[] 来记录结点是否在堆中,dis[i] 表示到第i个结点的最短距离

对于小根堆的操作还是基本的put()get() ,但由于有的结点已经在堆中了,所以可以把put() 拆为插入堆和调整位置两个部分

完整操作如下:

1.将与源点相邻的点进行松弛操作后加入堆

2.取出位于堆顶的结点

3.若取出的点为终点,则结束算法

4.将与当前结点相邻的点进行松弛操作

​ (1)如果该点已经在堆中,就调整在堆中的位置

​ (2)如果该点不在堆中,就加入堆

5.继续第二步

例题

最短路径问题

时间限制:1秒 内存限制:256兆

题目描述

平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间,其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的之间距离。现在的任务是找出一点到另一点之间的最短路径、

输入

输入共有n+m+3行,其中:

第一行为整数n

第2行到第n+1行(共n行),每行两个整数x和y,描述了一个点的坐标(以一个空格分隔)

第n+2行为一个整数m,表示图中连线的个数

此后的m行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线

最后一行:两个整数s和t,分别表示源点和目标点

输出

输出仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度

样例输入

5

0 0

2 0

2 2

0 2

3 1

5

1 2

1 3

1 4

2 5

3 5

1 5

样例输出

3.41

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 100+5 struct Edge//邻接表
{
int to;
double v;
Edge *next;
}; struct Node
{
int x,y;
}node[MAXN]; int n,m,pos[MAXN],heap_size,s,t,heap[MAXN];
double dis[MAXN];
Edge *first[MAXN];
bool in_heap[MAXN]; void add_edge(int u,int v,double len)
{
Edge *temp=new Edge;
temp->to=v;
temp->v=len;
temp->next=first[u];
first[u]=temp;
} void calc(int i,int j)
{
double len=sqrt(pow((double)(node[i].x-node[j].x),2)+pow((double)(node[i].y-node[j].y),2));
add_edge(i,j,len);
add_edge(j,i,len);
} void swapp(int i,int j)
{
int temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
pos[heap[j]]=j;//调整指针
pos[heap[i]]=i;
} void shift_up(int now)//调整位置
{
int next=0;
while(now>1)
{
next=now>>1;
if(dis[heap[next]]>dis[heap[now]])
swapp(next,now);
now=next;
}
} void put(int x)//插入堆
{
in_heap[x]=true;
heap[++heap_size]=x;
pos[x]=heap_size;
shift_up(heap_size);
} int get()//取堆顶元素
{
int now=1,next,res=heap[1];
in_heap[heap[1]]=false;
heap[1]=heap[heap_size--];
pos[heap[1]]=1;
while(now*2<=heap_size)
{
next=now<<1;
if(next<heap_size&&dis[heap[next+1]]<dis[heap[next]])
++next;
if(heap[now]<=heap[next])
return res;
swapp(now,next);
now=next;
}
return res;
} void dijkstra()
{
put(s);
dis[s]=0;
while(heap_size>0)
{
int top=get();
if(top==t)
break;
Edge *temp=first[top];
while(temp!=NULL)
{
if(dis[temp->to]>dis[top]+temp->v)
{
dis[temp->to]=dis[top]+temp->v;
//结点在堆中就只调整位置,否则插入堆并调整位置
if(in_heap[temp->to])
shift_up(pos[temp->to]);
else
put(temp->to);
}
temp=temp->next;
}
}
} int main()
{
int i,x,y;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d%d",&node[i].x,&node[i].y);
scanf("%d",&m);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
calc(x,y);
}
scanf("%d%d",&s,&t);
memset(dis,127,sizeof(dis));
dijkstra();
printf("%.2lf\n",dis[t]);
return 0;
}

Dijkstra算法的二叉堆优化的更多相关文章

  1. 最短路径——Dijkstra算法以及二叉堆优化(含证明)

    一般最短路径算法习惯性的分为两种:单源最短路径算法和全顶点之间最短路径.前者是计算出从一个点出发,到达所有其余可到达顶点的距离.后者是计算出图中所有点之间的路径距离. 单源最短路径 Dijkstra算 ...

  2. POJ 3635 - Full Tank&quest; - &lbrack;最短路变形&rsqb;&lbrack;手写二叉堆优化Dijkstra&rsqb;&lbrack;配对堆优化Dijkstra&rsqb;

    题目链接:http://poj.org/problem?id=3635 题意题解等均参考:POJ 3635 - Full Tank? - [最短路变形][优先队列优化Dijkstra]. 一些口胡: ...

  3. 二叉堆&lpar;一&rpar;之 图文解析 和 C语言的实现

    概要 本章介绍二叉堆,二叉堆就是通常我们所说的数据结构中"堆"中的一种.和以往一样,本文会先对二叉堆的理论知识进行简单介绍,然后给出C语言的实现.后续再分别给出C++和Java版本 ...

  4. 二叉堆&lpar;二&rpar;之 C&plus;&plus;的实现

    概要 上一章介绍了堆和二叉堆的基本概念,并通过C语言实现了二叉堆.本章是二叉堆的C++实现. 目录1. 二叉堆的介绍2. 二叉堆的图文解析3. 二叉堆的C++实现(完整源码)4. 二叉堆的C++测试程 ...

  5. 二叉堆&lpar;三&rpar;之 Java的实现

    概要 前面分别通过C和C++实现了二叉堆,本章给出二叉堆的Java版本.还是那句话,它们的原理一样,择其一了解即可. 目录1. 二叉堆的介绍2. 二叉堆的图文解析3. 二叉堆的Java实现(完整源码) ...

  6. 二叉堆的实现&lpar;数组)——c&plus;&plus;

    二叉堆的介绍 二叉堆是完全二元树或者是近似完全二元树,按照数据的排列方式可以分为两种:最大堆和最小堆.最大堆:父结点的键值总是大于或等于任何一个子节点的键值:最小堆:父结点的键值总是小于或等于任何一个 ...

  7. 图论——Dijkstra&plus;prim算法涉及到的优先队列(二叉堆)

    [0]README 0.1)为什么有这篇文章?因为 Dijkstra算法的优先队列实现 涉及到了一种新的数据结构,即优先队列(二叉堆)的操作需要更改以适应这种新的数据结构,我们暂且吧它定义为Dista ...

  8. 《Algorithms算法》笔记:优先队列&lpar;2&rpar;——二叉堆

    二叉堆 1 二叉堆的定义 堆是一个完全二叉树结构(除了最底下一层,其他层全是完全平衡的),如果每个结点都大于它的两个孩子,那么这个堆是有序的. 二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组 ...

  9. C&num; 最大二叉堆算法

    C#练习二叉堆算法. namespace 算法 { /// <summary> /// 最大堆 /// </summary> /// <typeparam name=&q ...

随机推荐

  1. iOS 隐藏状态栏

    1.整个项目隐藏状态栏 在Targets->General->勾选中Hide status bar . 整个项目隐藏状态栏 2.单个界面隐藏状态栏,例如登录注册页面 1.首先在info.p ...

  2. spring mvc 重定向问题

    (1)我在后台一个controller跳转到另一个controller,为什么有这种需求呢,是这样的.我有一个列表页面,然后我会进行新增操作,新增在后台完成之后我要跳转到列表页面,不需要传递参数,列表 ...

  3. Corba、protocol buffer、SOA的区别 (转)

    From: http://www.zhihu.com/question/20279489 Google的protocol buffers?这个跟corba.soa没啥关系,不同层次的概念,没法比.pr ...

  4. 一些记录查询的SQL语句

    -- ======================== 第三天 =========================== CREATE DATABASE php0408 CHARSET utf8 ;CR ...

  5. ARM处理器:开放者的逆袭

    作者:Vamei 出处:http://www.cnblogs.com/vamei 严禁转载. 1981年,英国BBC电视台策划了一系列关于计算机的电视节目.但导演发现一个问题:怎么给没见过电脑的观众画 ...

  6. 写给Android App开发人员看的Android底层知识(1)

    这个系列的文章一共8篇,我酝酿了很多年,参考了很多资源,查看了很多源码,直到今天把它写出来,也是战战兢兢,生怕什么地方写错了,贻笑大方. (一)引言 早在我还是Android菜鸟的时候,有很多技术我都 ...

  7. Python自学笔记-字符串编码(来自廖雪峰的官网Python3)

    感觉廖雪峰的官网http://www.liaoxuefeng.com/里面的教程不错,所以学习一下,把需要复习的摘抄一下. 以下内容主要为了自己复习用,详细内容请登录廖雪峰的官网查看.   1.理解变 ...

  8. Flex4之皮肤定制

    Flex4之皮肤定制[Skin类和Skin类]          博客分类: RIA-Flex4专栏 FlexAdobeUPFlashUI 第一.关于spark.skin.SparkSkin类的 1. ...

  9. Spring 整合WebSocket&comma; Error during WebSocket handshake&colon; Unexpected response code&colon; 302 还有200的错误

    springboot 集成websocket 及其简单,,,但是管理端使用的是Spring,原生配置,发生这个错误,,,302 被重定向了...我起的是本地locallhost,把ip换成 local ...

  10. centos中安装tomcat6

    在centos中安装tomcat6   1)通过yum自动安装tomcat和dependences root@Centos_AAA ~]# yum install tomcat6 [root@Cent ...