【学习笔记】dijkstra

一、dijkstra

1. 定义 & 作用

很简单。一个单源最短路算法。

2. 思想 & 实现

我觉得 sm 的图已经够了。

二、堆优化 dijkstra

1. 先来认识一下 proirity_queue

2. 如何使用 proirity_queue 对 dijkstra 优化？

每一步，我们都需要找到 \(d\) 值最小的节点（即 \(dis\) 值）以对其相邻节点进行松弛操作，而我们呢用了 proirity_queue 就可以快速找到 \(d\) 值最小的点了。

模板：

priority_queue<pii,vector<pii>,greater<pii> > q;
for(int i=1;i<=n;i++)
	dis[i]=inf;
dis[1]=0;
q.push({0,1});
while(!q.empty())
{
	pii now=q.top();
	q.pop();
	int mini=now.second;
	if(visit[mini]==1)continue;
	visit[mini]=1;
	for(int i=first[mini];i;i=e[i].next)
	{
		if(dis[mini]+e[i].w<dis[e[i].to])
		{
			dis[e[i].to]=dis[mini]+e[i].w;
			q.push({dis[e[i].to],e[i].to});
		}
	}
}