前言
Dijkstra算法可在$\mathcal O(m\log m)$或$\mathcal O(m\log n)$的时间内求解无负权单源最短路问题。本文中，我们将详细介绍算法的原理、实现，以及常用的两种优化。
另外，Dijkstra算法也不要乱用，比如说多源的最短路，用Dijkstra求解的复杂度只有$\mathcal O(nm\log m)$，但太麻烦，如果数据范围允许，直接用Floyd就能在$\mathcal O(n^3)$的时间内完成任务。
废话不多说，下面来看Dijkstra算法的流程。
流程
将结点分成两个集合：已确定最短路长度的点集（记为$S$集合）的和未确定最短路长度的点集（记为$T$集合）。一开始所有的点都属于$T$集合。
用$d_v$表示顶点$v$到起始点的距离、$s$表示起始点。
初始化$d_s=0$，其他点的$d$均为$+\infin$。
然后重复这些操作：
- 从$T$集合中，选取一个最短路长度最小的结点$v$，移到$S$集合中。
- 对于与$v$相邻的每个点$u$，执行松弛操作：
dis[u] = min(dis[u], dis[v] + G[v][u])。
直到$T$集合为空，算法结束。下面来看最简单的实现。
实现
本算法的代码可以在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]的路径往下逆序输出到达的点即可。
朴素实现（无优化）
这种实现完全按照算法流程，时间复杂度为$\mathcal O(n^2)$，无法通过例题。下面给出代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#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;
}
|
评测结果：
优先队列优化
优先队列，又称二叉堆，是常用的一种数据结构。可以执行下列操作（$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])$放入队列。
实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#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}$
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的优化不常用，但下面还是给出代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#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}$
后记
总结一下Dijkstra算法的实现方式：
- 暴力（$\mathcal O(n^2)$，TLE ;(）
- 优先队列（$\mathcal O(m\log m)$，$93\text{ms}$ :|）
- 集合/set（$\mathcal O(m\log n)$，$78\text{ms}$ :)）