dijkstra堆优化的小技巧

发表于 |

最短路是图论中非常常见的一种算法，一般来所，很多考试的第三题都会多多少少和最短路算法沾点边，而许多oier常用的是SPFA算法，也就是队列优化后的Bellman-Ford算法，但是实际上，这种算法具有非常大的不稳定性，也就是说，只要出题人愿意，他可以分分钟卡死你。所以一般考试时，只要数据没有到千万级别，一般我们会采用dijkstra堆优化的方式来写最短路。

所谓dijkstra，就是红白点的一种最短路算法，每次找到所有点中dis值最小的点，以其为起始点来更新其他点的dis值。一般来说，这种算法的实际复杂度为$n^2$,常数上不大(确信)，而我们发现，这里有一部是需要找到所有点中dis值的最小值，我们就可以使用对的方式来优化，可以将复杂度降至(nlogn)(实际上由于点数的膨胀，复杂度可能会超过$2nlogn$),那么在考场上，手写堆是十分耗时的，而且万一写错就彻底爆炸了，所有我们可以采用stl中的一种类堆结构：单调队列(priority_queue)来维护。

算法原理很简单，就是用单调队列来维护每次找寻的最小值，但是实际操作中却长长有一点小问题：
1.默认的stl是从大到小排列的，所以我们要重载小于号为大于号才能让其变成小根堆。

2.一般来说，这个算法每个点的dis值是在不断变化的，所以我们需要将每个变化的值，连同其坐标一起丢入单调队列之中，每次去除队首元素时，首先判断其是否被用过。

下面附代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=10001,maxm=500001;
struct node{
	int w,z;
}p;
bool operator<(node a,node b)
{
	return a.z>b.z;
}
struct Edge{
	int to,next,dis;
}edge[maxm];
int head[maxn],num_edge,dis[maxn],n,m,s,t,a,b,c,use[maxn];
void add_edge(int from,int to,int dis)
{
	edge[++num_edge].dis=dis;
	edge[num_edge].to=to;
	edge[num_edge].next=head[from];
	head[from]=num_edge;
}
priority_queue<node> q;
void push(int w)
{
	node a;
	a.w=w;
	a.z=dis[w];
	q.push(a);
}
void dijkstra(int s)
{
	push(s);
	while(!q.empty())
	{
		p=q.top();
		q.pop();
		if(use[p.w]==1)
		continue ;
		use[p.w]=1;
		for(int i=head[p.w];i;i=edge[i].next)
		{
			if(dis[edge[i].to]>dis[p.w]+edge[i].dis)
			dis[edge[i].to]=dis[p.w]+edge[i].dis,push(edge[i].to);
		}
	}
}
priority_queue<node> qwq;
void test()
{
	node a1,a2,a3;
	a1.w=1,a1.z=2;
	a2.z=4;
	a3.z=12;
	qwq.push(a1);
	qwq.push(a2);
	qwq.push(a3);
	cout<<qwq.top().z<<" ";
	qwq.pop();
	cout<<qwq.top().z<<" ";
	qwq.pop();
	cout<<qwq.top().z<<" ";
}
signed main()
{
	//test();
    cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
		dis[i]=2147483647;
	}
	dis[s]=0;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		add_edge(a,b,c);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<" ";
	}
	for(int i=1;i=n;i++)
	{
		cout<<dis[i]+
	}
}
-------------end.thanks for reading-------------