Dijkstra

给定一张 \(n\) 个点、\(m\) 条边的有向图，求 \(1\) 号点到每个点的最短路径长度。

我们用 \(dis_{i}\) 表示从点 \(1\) 到点 \(i\) 的最短距离。

• 初始化 \(dis_{1}\) 为 \(0\)，其余为无穷大

• 找出点 \(i\) ,满足 \(dis_{i}\) 是未标记节点中 \(dis\) 值最小的，并标记点 \(i\)

• 遍历节点 \(i\) 的出边，有点 \(i\) 到点 \(j\)，权值为 \(k\)。
  若 \(dis_{j}>dis_{i}+k\)，更新 \(dis_{j}\) 为 \(dis_{i}+k\)

• 重复第二第三步，标记到不能标记

如果起点不是 \(1\) ，就按需求调整起始点。

对于第二步，我们可以暴力循环但显然时间复杂度高，因此我们选用堆来存 \(dis\) 的值，以此优化，堆优化后的 Dijkstra 时间复杂度是 \(O(n\log n)\)，没有优化的是 \(O(n^2)\)。

不可以搞负权

Dijkstra粗浅的证明

因为边权都为非负数，所以选取的 \(dis\) 最小的结点不可能被其他点更新，故每次选出来的点 \(i\) 对应的 \(dis_{i}\) 一定是从起点到 \(i\) 的最短距离。

int n, m, u, v, w;
vector<int>to[MN], eg[MN];
int dis[MN]; bool vis[MN];
priority_queue<pair<int,int> >q;
void dij() {
	for(int i=1; i<=n; ++i) dis[i]=INF, vis[i]=0;
	dis[1]=0; q.push(make_pair(0,1)); 
	while(q.size()) {
		int x=q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x]=true;
		for(int i=0; i<to[x].size(); ++i) {
			int y=to[x][i], z=eg[x][i];
			if(dis[y]>dis[x]+z) { 
				dis[y]=dis[x]+z;
				q.push(make_pair(-dis[y],y));
			}
		} 
	}
}