Dijkstra算法

2025-08-30 15:21:07

发布于：上海

28阅读

0回复

0点赞

基本思路：
1、在dis数组里挑选一个离起点最近的点
2、用这个点更新其他点到起点的距离（松弛）

时间复杂度？ $\Theta(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});
				}
			} 
		}
	}