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\)。
然后重复这些操作：
- 从\(T\)集合中，选取一个最短路长度最小的结点\(v\)，移到\(S\)集合中。
- 对于与\(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算法的实现方式：