part1:dijkstra算法原理

贪心思想。每个点可能被更新多次，但最终每个点在更新成为最优时再取更新其他相邻点。

先看一个 \(DJ\) 代码片段：

struct node{
	int id,d;
	bool operator <(const node&a)const{
		return d>a.d;
	}
};
void dijkstra(int st){
	for(int i=1;i<=n;i++)
		dis[i]=0x3f3f3f3f;
	dis[st]=0;
	priority_queue<node>q;
	q.push((node){st,0});
	while(q.size()){
		int u=q.top().id;q.pop();
		if(vis[u]) continue; vis[u]=1;
		for(int e=head[u];e;e=edge[e].nex){
			int v=edge[e].to;
			if(dis[v]>dis[u]+edge[e].dis){
				dis[v]=dis[u]+edge[e].dis;
				q.push((node){v,dis[v]});
                cnt[v]++;
			}
		}
	}
}

大家猜一猜，若用这份代码跑上图，代码中的cnt[3]值应该是多少？

一个可能想错的小地方：DJ不是每个点只会被最短的那一条路径更新一次 \(dis\) 吗？所以cnt[3]==1。实际上答案可能为 \(2\) 。因为在点 \(1\)遍历出边时，点 \(3\) 可能先被遍历到了，然后才被点 \(2\) 遍历。

因此用 \(DJ\) 算法跑图论，有这样的一个性质：每个点可能入队多次，但只出队一次，且此时 \(dis[u]\) 已经被更新到了最优。这也是为什么要开一个vis数组来标记是否访问，同时是这个算法的理论基础。

part2:关于堆优化

是否有一些精通重载运算符的大佬喜欢这样写？

struct node{
	int id,d;
	bool operator <(const node&a)const{
		return dis[id]>dis[a.id];
	}
};
void dijkstra(int st){
	for(int i=1;i<=n;i++)
		dis[i]=0x3f3f3f3f;
	dis[st]=0;
	priority_queue<node>q;
	q.push((node){st,0});
	while(q.size()){
		int u=q.top().id;q.pop();
		if(vis[u]) continue;vis[u]=1;
		for(int e=head[u];e;e=edge[e].nex){
			int v=edge[e].to;
			if(dis[v]>dis[u]+edge[e].dis){
				dis[v]=dis[u]+edge[e].dis;
				q.push((node){v,dis[v]}); 
			}
		}
	}
}

注意到结构体 \(node\) 的小于运算符有一些不同了。

这样会出什么问题吗？首先，我们来了解一下 STL priority_queue​。

其内置一个堆。

如图是一个优先队列中的小根堆（第一维为点，第二维为其入队时的 \(dis\)，按第二维排序）。那么当我们像上面的代码一样写的话，\(dis\) 会被动态更新，而堆的结构却没有即使更新导致查询错误。

可供参考的代码

例题：P3371 【模板】单源最短路径（弱化版）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
const int M = 5e5+5;

int head[N],dis[N],cnt[N];
struct Edge{
	int nex,to,dis;
}edge[M];
struct node{
	int id,d;
	bool operator <(const node&a)const{
		return d>a.d;
	}
};
int n,m,s,elen;
bool vis[N];

void addedge(int from,int to,int dis){
	edge[++elen]={head[from],to,dis};
	head[from]=elen;
}
void dijkstra(int st){
	for(int i=1;i<=n;i++)
		dis[i]=0x3f3f3f3f;
	dis[st]=0;
	priority_queue<node>q;
	q.push((node){st,0});
	while(q.size()){
		int u=q.top().id;q.pop();
		if(vis[u])continue; vis[u]=1;
		for(int e=head[u];e;e=edge[e].nex){
			int v=edge[e].to;
			if(dis[v]>dis[u]+edge[e].dis){
				dis[v]=dis[u]+edge[e].dis;
				q.push((node){v,dis[v]}); 
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&s);
    for(int i=1,u,v,w;i<=m;++i)
        scanf("%d%d%d",&u,&v,&w),addedge(u,v,w);
    dijkstra(s);
    //for(int i=1;i<=n;++i)cout<<cnt[i]<<" ";
    for(int i=1;i<=n;++i)
        if(dis[i]!=0x3f3f3f3f)printf("%d ",dis[i]);
        else printf("2147483647 ");
	return 0;
} 

最后鸣谢：lost_heart_hurts大佬为本文提供代码。

The End.