Dijkstra算法
2025-05-31 13:21:37
发布于：上海
15阅读
0回复
0点赞
基本思路：
1、在dis数组里挑选一个离起点最近的点
2、用这个点更新其他点到起点的距离（松弛）
时间复杂度？ O ( m log n )
优先队列
priority_queue <node> pq;//默认大
pq.top();//默认最大——队列：q.front ()
pq.pop();
priority_queue<node,vector<node>,greater<node>> pq;//默认小
啊但是，最后一行这么写不太对劲，Node 咋排才是默认小呢？所以我们需要一个这个
struct node{
int dis,v;
friend bool operator < (node a,node b){
return a.dis>b.dis;
}
};
注意：1、在这个时候，priority_queue<node,vector<node>,greater<node>> pq;//默认小 就直接可以变成priority_queue <node> pq;
2、符号是反的
3、不能重载 >
dij代码示例
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push({0,s});
while(!q.empty()){
node t = q.top();
q.pop();
for(int j=1;j<=n;j++){
if(e[x][j]){
if(dis[j]>dis[x]+e[x][j]){
dis[j]=dis[x]+e[x][j];
q.push({dis[j],j});
}
}
}
}
有帮助，赞一个