最短路算法笔记

zyrddd / 2024-10-26 / 原文

最短路算法

最短路算法可大致分为三类：无负权边的单源最短路，有负权边的单源最短路和多源汇最短路

dijkstra 算法

dijkstra 算法是求无负权边的单源最短路的常用算法，基于贪心的思想

其过程大致为：

找到距离已经确定最短路的连通块的最近的点
把他加入已经确定最短路的连通块
用这个点去更新其他点的最短路

在此就不解释此算法的正确性

朴素版 dijkstra

我们可以看出，朴素版 dijkstra 的时间复杂度是 $ O(N^2) $ 的
对于每次找到距离距离已经确定最短路的连通块的最近的点这一步操作我们可以用堆来实现
因此我们就得到了堆优化版的 dijkstra

堆优化版 dijkstra

void dijkstra() {
	priority_queue<PII, vector<PII>, greater<PII>> pq;
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	pq.push({0, s});
	while (pq.size()) {
		auto t = pq.top();
		pq.pop();
		int ind = t.second;
		if (vis[ind]) continue;
		vis[ind] = true;
		for (int i = h[ind]; i != -1; i = ne[i]) {
			if (dis[e[i]] > t.first + w[i]) {
				dis[e[i]] = t.first + w[i];
				pq.push({dis[e[i]], e[i]});
			}
		}
	}
}

由于可以看出堆优化版 dijkstra 的时间复杂度是 $ O(MlogN) $ 的

所以我们在稠密图中跑朴素版 dijkstra ，在稀疏图中跑堆优化版 dijkstra