Dijkstra算法堆优化详解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Dijkstra算法堆优化详解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2025字，纯文字阅读大概需要3分钟。

内容图文

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[i])
        {
            int y=to[i];
            if(dist[y]>dist[x]+val[i])
            {
                dist[y]=dist[x]+val[i];
                q.push(make_pair(-dist[y],y));
            }
        }
    }
}

内容总结

以上是互联网集市为您收集整理的Dijkstra算法堆优化详解全部内容，希望文章能够帮你解决Dijkstra算法堆优化详解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---