用线段树写Dijikstra!!

句安
• 阅读 1506

速度是没有极限的。

众说周知,Dijikstra是一种最短路算法,复杂度为O(V^2+E)

朴素Dijikstra

void Dijikstra(int s){
  memset(dis,inf,sizeof(dis));
  dis[s]=0;
  for(int i=1;i<=n;++i){
    int maxs=inf,u=0;
    for(int j=1;j<=n;++j)
      if(!vis[j]&&dis[j]<maxs)
        maxs=dis[j],u=j;
    vis[u]=1;
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      if(dis[v]>dis[u]+w[e])
        dis[v]=dis[u]+w[e];
    }
  }
}

其实对于稠密图它还是很棒了。 但我们不满足于此。

常见优化-heap优化

这里我们采用STL_priority_queue进行优化

typedef pair<int,int> p;
priority_queue<p,vector<p>,greater<p> > q;
void Dijikstra(int s){
  memset(dis,inf,sizeof(dis));
  dis[s]=0;
  q.push(p(0,s));
  while(!q.empty()){
    const int u=q.top().second;
    q.pop();
    if(!vis[u]){
      vis[u]=1;
      for(int e=pre[u];e;e=nx[e]){
        const int v=to[e];
        if(!vis[v]&&dis[v]>dis[u]+w[e])
          dis[v]=dis[u]+w[e],
          q.push(p(dis[v],v));
      }
    }
  }
}

这样的话复杂度就到了O((V+E)logV) 但是,常数大。 手写堆比较复杂,不现实。

奇怪的优化-线段树优化

这并不是自己发现的,但是网上资料少就记录一下吧。 我们回头看看朴素的Dijikstra以及priority_queue优化。 发现优化的主要思路就是减少了查询当前dis最小点的复杂度。 那么也很容易想到用线段树来维护dis的最小值吧。 这样问题就变成了 整体最小值与单点修改,很简单的线段树操作吧。

int tree[N<<2],leaf;
/*线段树存的是点的标号*/
int check(int i,int j){
  return dis[i]<dis[j]?i:j;
}
void build(){
  memset(dis,inf,sizeof(dis));
  for(leaf=1;leaf<=n;leaf<<=1);--leaf;
  for(int i=1;i<=n;++i) tree[leaf+i]=i;
}
/*修改 dis[x] 为 y*/
void change(int x,int y){
  dis[x]=y,x+=leaf,x>>=1;
  while(x) tree[x]=check(tree[x<<1],tree[x<<1|1]),x>>=1;
}
void Dijikstra(int s){
  build();
  dis[s]=0;
  int u=s;
  for(int i=1;i<=n;++i){
    ans[u]=dis[u];
    change(u,max_int); /*删除u*/
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      if(dis[v]>ans[u]+w[e])
        change(v,ans[u]+w[e]);
    }
    u=tree[1];
  }
}

这个比堆短吧。 而且非递归的线段树常数也很小呢。

测试&总结

以luogu的单源最短路模板题(稀疏图,无O2)作为测试。

  • 朴素的Dijikstra 2000+ms
  • Dijikstra+priority_queue 652ms
  • Dijikstra+线段树 192ms 然后加11了SLF和LLL的SPFA也很快,大概300ms

所以SPFA和Dijikstra+priority_queue是很实用的,但如果想卡排名的话可以试一试线段树啊

--来自xb神犇

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Easter79 Easter79
3年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
Karen110 Karen110
4年前
人工智能数学基础8:两个重要极限及夹逼定理
一、极限公式1二、极限公式2e为常数2.71828…变体:使用案例:三、夹逼定理夹逼定理英文原名SqueezeTheorem,也称两边夹定理、夹逼准则、夹挤定理、挟挤定理、三明治定理,是判定极限存在的两个准则之一。是法国著名数学家、物理学家约瑟夫·路易斯·拉格朗日(JosephLouisLagrange,17361813)提出的。3.1、数
Wesley13 Wesley13
3年前
HDU2544用矩阵实现的Dijkstra
 include<iostreamusingnamespacestd;introad105105,dis105,n;boolIn105;intDijkstra(intstart,intend);intmain(){intm,a,b,c
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
美凌格栋栋酱 美凌格栋栋酱
5个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
菜园前端 菜园前端
2年前
什么是时间复杂度?
原文链接:什么是时间复杂度?定性描述该算法的运行时间,一个函数、用大O表示,例如O(1)、O(n)、O(logN)...常见的时间复杂度量级常数阶O(1)对数阶O(logN)线性阶O(n)线性对数阶O(nlogN)平方阶O(n²)立方阶O(n)K次方阶O(
菜园前端 菜园前端
2年前
什么是空间复杂度?
原文链接:什么是空间复杂度?算法在运行过程中临时占用存储空间大小的度量,和时间复杂度表示一样,一个函数,用大O表示,例如O(1)、O(n)、O(^2)...基础案例O(1)这段代码因为只声明了单个变量,单个变量所占用的内存永远是1。javascriptle
菜园前端 菜园前端
2年前
什么是顺序搜索?
原文链接:什么是顺序搜索?顺序搜索是一种比较低效的搜索算法,但是实现起来相对简单。主要步骤如下:1.遍历数组2.找到跟目标值相等的元素,就返回它的下标3.遍历结束后,如果没有搜索到目标值,则返回1基础案例时间复杂度:O(n)空间复杂度:O(1)javasc
深入理解线段树 | 京东物流技术团队
线段树(SegmentTree)是常用的维护区间信息的数据结构,它可以在O(logn)的时间复杂度下实现单点修改、区间修改、区间查询(区间求和、区间最大值或区间最小值)等操作,常用来解决RMQ问题。RMQ(RangeMinimum/MaximumQuery