Dijkstra 最短路

Dijkstra 算法特点

优点

带有堆优化的 Dijkstra 算法时间复杂度为 $O(m\log m)$ ，速度较快；
Dijkstra 的算法思路清晰易懂，非常好写。

缺点

Dijkstra 是一种单源最短路算法，仅能求解图中单点到其他点的距离；
Dijkstra 算法仅能求解边权全部为非负数的最长路问题，同理，也不能判断负环。

Dijkstra 算法思路

核心思想

穷则独善其身，达则兼济邻居。

实现过程

通过高度提炼的核心思想，我们可以看出 Dijkstra 的大致实现过程，如果一个点可以个更新与其邻接的点，那么就使用它去对邻接的节点进行松弛操作（即利用现有最短路求解更新邻接节点）。

具体过程

朴素做法

对于需要求解最短路的源点 $s$ ，我们要求解的就是所有节点到节点 $s$ 的最短路径，所以令 $s$ 号点的距离为 $0$ ，其他点的距离全为 $inf$ ，并且，用 $dis[s]=0$ 来更新 $s$ 节点的所有邻接的节点。
对于所有更新过的节点，在用他们去更新邻接的节点，知道更新完成为止。

这样做的话就类似于 Shortest Path Fast Algorithm（SPFA）了，对于一张稠密图，如果我们的松弛顺序不得当，那么有可能会被卡到 O(nm)，那么，考虑什么样的点最适合更新其他的点？

贪心优化

考虑贪心，每次使用目前距离最小的点进行松弛，那么，如果我们暴力的枚举每个点的距离，从而找到最小点，这样每次松弛时间仅仅用于找距离最小的点的复杂度就已经是 $O(n)$ 了，再进行 $n$ 轮松弛，效率为 $O(n^2)$ ，不够理想。

但是，找最小的点这种操作可以使用数据结构优化，维护最小值的最简便也较迅速的维护方式就是堆，也就是优先队列（STL 中的 priority_queue），每次取出小根堆的堆顶元素，在对于其所邻接的节点进行更新即可。

需要注意的是，如果一个点被他的邻接节点松驰过了，我们就应当把它加入堆中，但是由于每个点的入堆顺序和出堆顺序不同，每次拿出的一定是它在多次松弛所到的距离中最小的，显然的，用最小值取松弛一定是最好的，所以一个点只要出堆一次，如果我们下次发现一个节点第二次出堆，那么这次出堆的结果一定不比上次优，直接从堆中删除，不要用它来松弛，因为他什么都松弛不了，白跑一边还浪费时间。

时间复杂度

用堆优化 Dijkstra 算法，每个节点虽然最多在堆中出堆一个，但有可能入堆多次，所有节点总的被松弛次数和（入堆次数）在最坏情况下可以达到 $m$ 次，而对于每个结点的松弛，我们总共要遍历 $m$ 条边，总的时间复杂度为 $O(m\log m)$

Dijkstra+堆优化代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+6, M = 2e5+6;
int hd[N],tot;
struct node {
	int to,wt,nx;
} eg[M<<1];
void adeg(int st,int ed,int wt) {
	eg[++tot]={ed,wt,hd[st]};
	hd[st]=tot;
}
int dis[N];
bitset<N> vis;
void dijkstra(int s) {
	memset(dis,0x3f,sizeof dis); //初始化为 inf
	priority_queue<pair<int,int> > pq; //使用 stl 的优先队列
	dis[s]=0; //将 s 节点的 dis 值初始化为 0
	pq.push({0,s}); //将 s 节点入堆
	while(pq.size()) {
		auto tp=pq.top(); //取出堆顶
		pq.pop();
		int st=tp.second;
		if(vis[st]) continue; //如果这个点已经出堆过了，那么这次一定不优，直接跳过
		vis[st]=true;
		for(int i=hd[st];i;i=eg[i].nx) {
			int to=eg[i].to,wt=eg[i].wt;
			if(dis[st]+wt<dis[to]) {
                //如果可以更新 dis[to]，那么就执行松弛操作
				dis[to]=dis[st]+wt;
				pq.push({-dis[to],to});
                //stl 当中的堆默认是大根堆，这里为了省事直接往里传负数即可
			}
		}
	}
}
int main() {
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i) {
		int u,v,w;
		cin>>u>>v>>w;
		adeg(u,v,w); //加边操作
		adeg(v,u,w); //如果是有向图就删掉这一行
	} dijkstra(s); //对于源点 s 求解最短路
	for(int i=1;i<=n;++i) cout<<dis[i]<<' ';
	return 0;
}