> 源代码2213字,渲染后2102字。
前言
作者在学习最短路算法时发现没有讲堆优化 Dij 的帖子,遂手搓一帖。
什么你没学过 Dij ?去吃这个吧https://www.acgo.cn/discuss/post/59252
> 内容 100% 人工制作,不含任何AI成分,糖分低更健康。
正文
前言
堆优化 Dijkstra(也被称为优先队列优化),优化了 Dijkstra 算法中寻找当前距离最短顶点的部分。( O(N)−>O(logN)O(N) -> O(logN)O(N)−>O(logN) )
可一定程度上提升 Dijkstra 的运行速度。
思路
> 以下代码中,g为邻接表存图(存图方式见下),dis为距离,vis表示是否被访问过。
> 学校电脑无法截图,故不提供图片。
在朴素 Dijkstra 中,一般使用以下代码(或类似)寻找当前距离起点最短的顶点(cur):
时间复杂度: O(N)O(N)O(N)
显然,cur一定是一个被松弛过且vis[cur]==0的点。
所以,考虑将满足以上条件的点加入一个小根堆,这样取最小点就变成了
时间复杂度:O(logN)O(logN)O(logN)
代码实现
> 此处,pii代表pair<int,int>。
> 代码实现不包含建图。要观看建图,跳转至下文例题。
首先建立小根堆。
因为pair根据first进行排序,所以priority_queue里的pair存储数据如{当前距离,当前顶点} 。
初始化,起点入堆。
代码主体部分(参考注释食用):
这就是堆优化 Dij 的核心。
例题
> 写到这里突然发现原例题是团队题,不得已选了个别的。其实原例题是这题弱化版(
> 这题数据貌似要开 long long ,但是实测发现太水了,int 也能过。
A569.单源最短路径1
原例题是此题弱化版。
显然板子,注意一下数据范围。
100pts。100pts。100pts。
后记
无。