#创作计划#堆优化Dijkstra算法
2026-02-28 15:25:04
发布于：广东
源代码2213字，渲染后2102字。
前言
作者在学习最短路算法时发现没有讲堆优化 Dij 的帖子，遂手搓一帖。
什么你没学过 Dij ？去吃这个吧https://www.acgo.cn/discuss/post/59252
内容 100% 人工制作，不含任何AI成分，糖分低更健康。
正文
前言
堆优化 Dijkstra（也被称为优先队列优化），优化了 Dijkstra 算法中寻找当前距离最短顶点的部分。（ ）
可一定程度上提升 Dijkstra 的运行速度。
思路
以下代码中，
g为邻接表存图（存图方式见下），dis为距离，vis表示是否被访问过。
学校电脑无法截图，故不提供图片。
在朴素 Dijkstra 中，一般使用以下代码（或类似）寻找当前距离起点最短的顶点（cur）：
int cur = 0;
for(int i = 1;i <= n;i++){
if(dis[i]<dis[cur] && !vis[i]){
cur=i;
flag=1;
}
}
时间复杂度：
显然，cur一定是一个被松弛过且vis[cur]==0的点。
所以，考虑将满足以上条件的点加入一个小根堆，这样取最小点就变成了
auto cur = pq.top();
pq.pop();
时间复杂度：
代码实现
此处，
pii代表pair<int,int>。
代码实现不包含建图。要观看建图，跳转至下文例题。
首先建立小根堆。
因为pair根据first进行排序，所以priority_queue里的pair存储数据如{当前距离,当前顶点} 。
priority_queue<pii,vector<pii>,greater<pii> > pq;
初始化，起点入堆。
memset(dis,0x3f,sizeof dis);
dis[s]=0;
pq.push({0,s});
代码主体部分(参考注释食用)：
while(pq.size()){
auto cur = pq.top();
pq.pop();//cur格式如上所示
if(vis[cur.second])continue;//将对 vis 的判断放在这里，原因见上。
vis[cur.second]=1;//标记vis
int w=cur.first,u=cur.second;//取出：w 当前点距离; u 当前点编号
for(auto i : g[u]){//遍历相邻边 注：g[u] 是一个vector<pii>,其中 first 为边终点，second 为边权
if(dis[i.first]>w+i.second){
dis[i.first]=w+i.second;
pq.push({dis[i.first],i.first});//更新，入队。
}
}
}
这就是堆优化 Dij 的核心。
例题
写到这里突然发现原例题是团队题，不得已选了个别的。其实原例题是这题弱化版（
这题数据貌似要开long long，但是实测发现太水了，int也能过。
A569.单源最短路径1
原例题是此题弱化版。
显然板子，注意一下数据范围。
#include<bits/stdc++.h>
using namespace std;
const int N = 1010000;
typedef pair<int,int> pii;
vector<pii> g[N];
int n,m,s;
int vis[N],dis[N];
int main(){
//见题面
cin >> n >> m >> s;
//有向图建图（邻接表）
for(int i = 1;i <= m;i++){
int u,v,w;cin >> u >> v >> w;
g[u].push_back({v,w});
}
//初始化为极大值
memset(dis,0x3f,sizeof dis);
dis[s]=0;
//priority_queue默认大根堆，需要调整。
//因为pair根据first进行排序，所以priority_queue里的pair存储数据如下：{当前距离,当前顶点}
priority_queue<pii,vector<pii>,greater<pii> > pq;
pq.push({0,s});
while(pq.size()){
auto cur = pq.top();
pq.pop();
if(vis[cur.second])continue;
vis[cur.second]=1;
int w=cur.first,u=cur.second;
for(auto i : g[u]){
if(dis[i.first]>w+i.second){
dis[i.first]=w+i.second;
pq.push({dis[i.first],i.first});
}
}
}
for(int i = 1;i <= n;i++){
cout << (dis[i]==0x3f3f3f3f?-1:dis[i]) << ' ';
}
}
后记
无。
全部评论 5
与最短路算法无关，只是优化了数据结构。斐波那契堆可以自己去搜，支持 插入一个值， 查询值和减小一个数的值（注意这里是均摊时间复杂度）原先的迪杰斯科拉可能会将一个点反复松弛，堆内最多元素数是边数，因为在一个值改变时只能再次插入它。斐波那契堆能把 前面的 M 换成 N
2026-02-28 来自 广东
0
有帮助，赞一个