【算法笔记】单源最短路问题——Dijkstra算法（无优化/优先队列/set优化）

0. 前言

Dijkstra算法可在$\mathcal O(m\log m)$或$\mathcal O(m\log n)$的时间内求解无负权单源最短路问题。本文中，我们将详细介绍算法的原理、实现，以及常用的两种优化。

另外，Dijkstra算法也不要乱用，比如说多源的最短路，用Dijkstra求解的复杂度只有$\mathcal O(nm\log m)$，但太麻烦，如果数据范围允许，直接用Floyd就能在$\mathcal O(n^3)$的时间内完成任务。

废话不多说，下面来看Dijkstra算法的流程。

1. 流程

将结点分成两个集合：已确定最短路长度的点集（记为$S$集合）的和未确定最短路长度的点集（记为$T$集合）。一开始所有的点都属于$T$集合。

用$d_v$表示顶点$v$到起始点的距离、$s$表示起始点。
初始化$d_s=0$，其他点的$d$均为$+\infin$。

然后重复这些操作：

1. 从$T$集合中，选取一个最短路长度最小的结点$v$，移到$S$集合中。
2. 对于与$v$相邻的每个点$u$，执行松弛操作：dis[u] = min(dis[u], dis[v] + G[v][u])。

直到$T$集合为空，算法结束。下面来看最简单的实现。

2. 实现

本算法的代码可以在CF20C/洛谷链接提交。后面提供的参考代码的输入输出格式都是基于这道题的。数据范围：$n,m\le 10^5,w_i\le 10^6$。

在编写代码之前，我们还要考虑一个问题：如何输出最短路径？
定义一个数组$\mathrm{par}$，$\mathrm{par}[i]$表示最短路径上在点$i$前面的点。初始时，$\mathrm{par}[s]=-1$，表示前面没有点。

在$v\to u$这条边上更新dis[u] = dis[v] + G[v][u]时，同时更新par[u] = v，最后输出时顺着par[v]的路径往下逆序输出到达的点即可。

2.1 朴素实现（无优化）

这种实现完全按照算法流程，时间复杂度为$\mathcal O(n^2)$，无法通过例题。下面给出代码。

#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 100005
using namespace std;

vector<pair<int, int>> G[maxn];

long long dis[maxn];
int par[maxn];
bool vis[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		G[--u].emplace_back(--v, c);
		G[v].emplace_back(u, c);
	}
	// Dijkstra 算法流程
	// 初始化
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[0] = 0LL, par[0] = -1; // 起点的距离为0
	while(true)
	{
		int v = n; // 不存在的虚拟结点，距离为+INF，方便判断
		for(int i=0; i<n; i++)
			if(!vis[i] && dis[i] < dis[v])
				v = i;
		if(v >= n - 1) break; // 找不到或到达终点，退出
		vis[v] = true; // 标记访问过
		for(auto [u, d]: G[v])
			if(dis[v] + d < dis[u]) // 是否有更优路径？
			{
				dis[u] = dis[v] + d; // 更新距离
				par[u] = v; // 更新路径
			}
	}
	if(dis[n - 1] == dis[n]) // 没有找到解（图不连通）
	{
		puts("-1");
		return 0;
	}
	vector<int> path; // 存储路径，注意要倒序输出
	int v = n - 1; // 从终点向前获取最优路径
	while(v != -1)
	{
		path.push_back(v); // 加入路径
		v = par[v]; // 向前回溯
	}
	for(int i=path.size()-1; i>=0; i--)
		printf("%d ", path[i] + 1); // 输出
	return 0;
}

评测结果：

2.2 优先队列优化

优先队列，又称二叉堆，是常用的一种数据结构。可以执行下列操作（$n$为优先队列队列中的元素个数）：

• 弹出最小/最大的元素，时间$\mathcal O(\log n)$
• 添加新元素，时间$\mathcal O(\log n)$

利用这些特点，我们可以在$\mathcal O(m\log m)$的时间内完成一轮Dijkstra。其细节为：

• 初始时，仅将起始点和距离$(s,0)$放入队列；
• 当队列不为空时，执行：
  • 弹出距离最小的顶点和距离$(v,d)$，如果距离$d\ne dis[v]$，则说明已经找到了其他更短路径，舍弃这条路；
  • 否则，依次更新每条邻边$v\to u$，如果距离比原来的更短，则不仅要更新$\mathrm{dis}$和$\mathrm{par}$，还要把$(u,\mathrm{dis}[u])$放入队列。

实现代码：

#include <cstdio>
#include <queue>
#define maxn 100005
#define INF 9223372036854775807LL
using namespace std;

using LL = long long;
using pli = pair<LL, int>;

vector<pair<int, int>> G[maxn];
LL dis[maxn];
int par[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		G[--u].emplace_back(--v, c);
		G[v].emplace_back(u, c);
	}
	for(int i=1; i<n; i++) dis[i] = INF;
	par[0] = -1;
	priority_queue<pli, vector<pli>, greater<pli>> q;
	q.emplace(0LL, 0);
	while(!q.empty())
	{
		auto [d, v] = q.top(); q.pop();
		if(dis[v] == d)
			for(auto [u, w]: G[v])
				if(d + w < dis[u])
					par[u] = v,
					q.emplace(dis[u] = d + w, u);
	}
	if(dis[n - 1] == INF) { puts("-1"); return 0; }
	vector<int> path;
	int v = n - 1;
	while(v != -1)
	{
		path.push_back(v);
		v = par[v];
	}
	for(int i=path.size()-1; i>=0; i--)
		printf("%d ", ++path[i]);
	return 0;
}

时间复杂度为$\mathcal O(m\log m)$，可以通过此题。运行时间：$93\text{ms}$

2.3 set优化

set又称集合，与优先队列相似，支持添加、删除，另外还可以删除任意元素，时间$\mathcal O(\log n)$。要发挥出set的优势，就要在维护时删掉多余的顶点-距离对，防止不必要的dis[v] == d这种判断。

此时，集合中的元素个数永远不会超过$N$，因此总时间复杂度为$\mathcal O(m\log n)$。
在$m\ge n$，即边数大于顶点数时，这种方法优于priority_queue。不过，一般使用Dijkstra算法的题目中都是$m\le n$，所以set的优化不常用，但下面还是给出代码。

#include <cstdio>
#include <vector>
#include <set>
#define maxn 100005
#define INF 9223372036854775807LL
using namespace std;

using LL = long long;
using pli = pair<LL, int>;

vector<pair<int, int>> G[maxn];
LL dis[maxn];
int par[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		G[--u].emplace_back(--v, c);
		G[v].emplace_back(u, c);
	}
	for(int i=1; i<n; i++) dis[i] = INF;
	par[0] = -1;
	set<pli> s;
	s.emplace(0LL, 0);
	while(!s.empty())
	{
		auto it = s.begin(); s.erase(it);
		auto [d, v] = *it;
		for(auto [u, w]: G[v])
			if(d + w < dis[u])
			{
				par[u] = v;
				if(dis[u] != INF)
					s.erase(pli(dis[u], u));
				s.emplace(dis[u] = d + w, u);
			}
	}
	if(dis[n - 1] == INF) { puts("-1"); return 0; }
	vector<int> path;
	int v = n - 1;
	while(v != -1)
	{
		path.push_back(v);
		v = par[v];
	}
	for(int i=path.size()-1; i>=0; i--)
		printf("%d ", ++path[i]);
	return 0;
}

AC，运行时间：$78\text{ms}$

3. 后记

总结一下Dijkstra算法的实现方式：

• 暴力（$\mathcal O(n^2)$，TLE 😭）
• 优先队列（$\mathcal O(m\log m)$，$93\text{ms}$ 😐）
• 集合/set（$\mathcal O(m\log n)$，$78\text{ms}$ 😃）

if(hasSanLian()) cout << "Thank you!";