优先队列 + Dijkstra算法
2025-05-31 13:49:58
发布于：上海
11阅读
0回复
0点赞
1，优先队列:
//1,大的优先
priority_queue<int> q;
//2,小的优先
priority_queue<int,vevtor<int>,greater<int> > q;
q.top();//取最大/小值
q.pop();//删除最大/小值
当遇到struct node类型是要加一些代码来操作优先队列:
struct node{
int dis,v;//权值 , 终点
friend bool operator < (node a , node b){
return a.dis > b.dis ;//小的优先
}
};
//反之则大的优先
2，Dijkstra算法基础代码（有向图）
#include<bits/stdc++.h>
using namespace std;
int n,m,s,e[5005][5005],dis[5005],vis[5005];//节点个数，边数，起点 ，边的权值，边到起点的最短路 ，访问记录
void dij(){
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
for(int i=1;i<=n;i++){//做n次操作
//1，选点 在dis数组中找到未被用过的最小的点
int u = 0;//最后选出来的点
for(int j=1;j<=n;j++){
if(!vis[j] && dis[j] < dis[u])
u = j;
}
vis[u] = 1;
//2，松弛
//遍历选出来的点，周围邻居
//更新这些邻居到起点的距离
//更新邻接矩阵e中第u行的每一列
for(int j=1;j<=n;j++){
if(e[u][j]){//不为0说明可走
int v = j;//终点
int w = e[u][j];//权值
if(dis[v] > dis[u] + w)//可更新
dis[v] = dis[u] + w;
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(!e[u][v])
e[u][v] = w;//v到u的距离为w
else
e[u][v] = min(e[u][v] , w);
}
dij();//dijkstra函数
for(int i=1;i<=n;i++){
if(dis[i] == 0x3f3f3f3f)cout<<-1<<" ";
else cout<<dis[i]<<" ";
}
return 0;
}
3，优化代码(T45256.dijkstra堆优化版本)
#include<bits/stdc++.h>
using namespace std;
int n,m,dis[100005],vis[100005];
struct edge{
int dis,v;//权值 , 终点
friend bool operator < (edge a , edge b){
return a.dis > b.dis ;//小的优先
}
};
struct node{
int wg,to;//这条边的权值和要到达的点
};
vector<node> v[100005];
priority_queue<edge> q;
void dij(){
memset(dis,0x3f,sizeof(dis));
dis[1] = 0;
q.push({0,1});
while(!q.empty()){
//选点
edge t = q.top();//取最小值
q.pop();
//判断是否被访问过
int x = t.v ;
if(vis[x])continue;
vis[x] = 1;
//松弛
for(int j=0;j<v[x].size();j++){
int y = v[x][j].to;
int w = v[x][j].wg;
if(dis[y] > dis[x] + w ){
dis[y] = dis[x] + w;
q.push({dis[y],y});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({z,y});
}
dij();
for(int i=1;i<=n;i++){
if(dis[i] == 0x3f3f3f3f)cout<<-1<<" ";
else cout<<dis[i]<<" ";
}
return 0;
}
有帮助，赞一个