算法：Dijkstra算法堆优化详解

闲鱼技术01 · 发表于 2022-8-31 12:59

DIJ算法的堆优化

DIJ算法的时间复杂度是 O(n^2) 的，在一些题目中，这个复杂度显然不满足要求。所以我们需要继续探讨DIJ算法的优化方式。
堆优化的原理

堆优化，顾名思义，就是用堆进行优化。我们通过学习朴素DIJ算法，明白DIJ算法的实现需要从头到尾扫一遍点找出最小的点然后进行松弛。这个扫描操作就是坑害朴素DIJ算法时间复杂度的罪魁祸首。所以我们使用小根堆，用优先队列来维护这个“最小的点”。从而大大减少DIJ算法的时间复杂度。
堆优化的代码实现

说起来容易，做起来难。
我们明白了上述的大体思路之后，就可以动手写这个代码，但是我们发现这个代码有很多细节问题没有处理。
首先，我们需要往优先队列中push最短路长度，但是它一旦入队，就会被优先队列自动维护离开原来的位置，换言之，我们无法再把它与它原来的点对应上，也就是说没有办法形成点的编号到点权的映射。
我们用pair解决这个问题。
pair是C++自带的二元组。我们可以把它理解成一个有两个元素的结构体。更刺激的是，这个二元组有自带的排序方式：以第一关键字为关键字，再以第二关键字为关键字进行排序。所以，我们用二元组的first位存距离，second位存编号即可。
然后我们发现裸的优先队列其实是大根堆，我们如何让它变成小根堆呢？
有两种方法，第一种是把第一关键字取相反数，取出来的时候再取相反数。第二种是重新定义优先队列：
priority_queue<int,vector<int>,greater<int> >q;
解决了这些问题，我们愉快地继续往下写，后来我们发现，写到松弛的时候，我们很显然要把松弛后的新值也压入优先队列中去，这样的话，我们又发现一个问题：优先队列中已经存在一个同样编号的二元组（即第二关键字相同），我们没有办法删去它，也没有办法更新它。那么在我们的队列和程序运行的时候，一定会出现bug。
怎么办呢？？
我们在进入循环的时候就开始判断：如果有和堆顶重复的二元组，就直接pop掉，成功维护了优先队列元素的不重复。
所以我们得到了堆优化的代码：
priority_queue<pair<int,int> >q;
void dijkstra(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(v,0,sizeof(v));
dist[start]=0;
q.push(make_pair(0,start));
while(!q.empty())
{
      while(!q.empty() && (-q.top().first)>dist[q.top().second])
         q.pop();
      if(!q.empty())
         return;
      int x=q.top().second;
      q.pop();
      for(int i=head[x];i;i=nxt)
      {
         int y=to;
         if(dist[y]>dist[x]+val)
         {
            dist[y]=dist[x]+val;
            q.push(make_pair(-dist[y],y));
         }
      }
}
}
UPD：2020.10.28
现在又回头来看这个模板，还是觉得很麻烦的。至少很多东西实现的时候很是繁琐。
其实我们完全可以使用标记数组来避免重复关键字的多次更新。
所以我们得到了新的Dijkstra模板。
void dijkstra()
{
memset(dist,127,sizeof(dist));
dist[1]=0;
q.push(make_pair(0,1));
while(!q.empty())
{
      int x=q.top().second;
      q.pop();
      if(v[x])
         continue;
      v[x]=1;
      for(int i=head[x];i;i=nxt)
      {
         int y=to;
         if(dist[y]>dist[x]+val)
         {
            dist[y]=dist[x]+val;
            q.push(make_pair(-dist[y],y));
         }
      }
}
}

		自动登录	找回密码
密码			立即注册