简介

Dijkstra算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。

算法描述

文字描述

令图为 G=(V,E)，其中 E[i] 的权值为 w[i]。

令集合 S 为已找到最短路径的点集，集合 U 为 S 在 V 中的补集。

dist[i] 为点 i 距起点的最短距离，起点为 s_0。

1. 令 S=\emptyset，dist[s_0]=0，其余的点 dist[i] = INF。
2. 设 i 为 U 中 dist 值最小的点，将 i 加入 S。
3. 更新集合 U 中 i 的邻居点 j 的 dist， 更新方式为 dist[j] = min(dist[j],dist[i] + w(i, j))。
4. 如果 U==\emptyset 或者 dist[U] 均等于INF，退出。
5. 重复2步骤。

图解

• 设 A 为起点。

• 选择 A，更新 B,C,D。

• 选择 C，更新 B,E。

• 选择 B，更新 D。

• 选择 D，发现 E 不必更新。

• 选择 E，算法终止。

数学证明

可以用数学归纳法(此证明是在不存在负边权的前提下)：

1. 首先起点本身距自己距离一定最短。
2. 令前 k 个点的 dist 为实际的最短距离，加入第 k + 1 个点时。
   利用反证法，假设第 k + 1个点的实际距离为 L_{k+1} 且 L_{k+1} < dist[k + 1]，设 k 的前驱为 j 且 j \not\in S 。
   因为 dist[j] \geq dist[k + 1] 且 w(j, k + 1) \geq 0，所以 L_{k+1} = dist[j] + w(j,k+1) \geq dist[k+1]，与假设矛盾。
3. 所以该算法成立。

算法优化

复杂度分析：大循环要将每个点加入 S 一次，需要 O(n) 的复杂度。加入每个点时存在一个更新操作，复杂度与边的存储方式有关，然后寻找 U 中 dist 最小的点需要 O(n) 的遍历。
所以总复杂度为 O(n^2)。

如果每次更新时，将更新的 dist 值push到小根堆里面，那么每次取出堆顶的元素来执行更新操作即可。最多需要push m 次，每次 O(log_m)，取出 m 次，每次 O(1)。
所以总复杂度为 O(mlog_m)。

于是，可以在稀疏图中可以用堆优化的Dijkstra算法，稠密图不必优化。

代码

点数为 n， 边数为 m，起点为 s。
以下采用链式向前星存图。

struct edge {
	int to, next; ll w;
}e[M * 2];
int id, head[N];
void add(int x, int y, int w) {
	e[++id] = (edge){y, head[x], w}; head[x] = id;
	// e[++id] = (edge){x, head[y], w}; head[y] = id;
}
int n, m, s;
ll dist[N];
bool vis[N];

• Dijkstra

void dijkstra() {
	for (int i = 1; i <= n; i++) dist[i] = INF;
	dist[s] = 0;
	ll mi;
	while(!vis[s]){
		vis[s] = true;
		for (int i = head[s], to = e[i].to; i; i = e[i].next, to = e[i].to)
			if(!vis[to] && dist[to] > dist[s] + e[i].w)
				dist[to] = dist[s] + e[i].w;
		mi = INF;
		for (int i = 1; i <= n; i++)
			if(!vis[i] && mi > dist[i]) {
				mi = dist[i];
				s = i;
			}
	}
}

• 堆优化 + Dijkstra

struct node{
	int u; ll d;
	bool operator<(const node& a) const{ return d > a.d; }
}; 
priority_queue<node> q;
void dijkstra() {
	for (int i = 1; i <= n; i++) dist[i] = INF;
	dist[s] = 0;
	q.push((node){s, dist[s]});
	while (!q.empty()) {
		s = q.top().u; q.pop();
		if (vis[s]) continue; vis[s] = 1;
		for (int i = head[s], to = e[i].to; i; i = e[i].next, to = e[i].to)
			if(!vis[to] && dist[to] > dist[s] + e[i].w){
				dist[to] = dist[s] + e[i].w;
				q.push((node){to, dist[to]});
			}
	}
}