1. 概述
Dijkstra算法（通称迪杰斯特拉算法）是一个经典的单源最短路算法，可用于非负权有向图或非负权无向图，用于计算从某个节点开始到全图其他每一个节点的最短路长度（以及最短路具体路径）。
对于图$G(V, E)$（$V$是节点集合，$E$是边集合），算法的时间复杂度是$O(ElogE)$。
在理解dijkstra算法时，可能会遇到一些疑难点，如“是不是按照这个顺序排列？”或者“为什么这样就能找到答案？”或者“如果变成这样的图，还能得到最短路吗？”等等。如果不彻底理解这些疑难点，会在解决单源最短路径的各种变种问题时感到迷惑。
本文解释了这些疑难点，并在最后给出Dijkstra算法的C++实现。
2. 算法简述
为了便于描述，先定义几个仅限本文的术语。
| 术语 |
含义 |
| $G$ |
带权图，可能有向或无向，但权值非负。 |
| $V$ |
图$G$中的所有节点的集合。 |
| $E$ |
图$G$中的所有边的集合。 |
| $s$ |
源节点。是$V$中的一个节点，本算法要计算从$s$到$V$中其他节点的最短路径。 |
| 全图最短路 |
在$G$中，从源节点$s$到任一节点$u$会有多条长度不同的路径。考察所有路径后，最短的那条，就是从$s$到$u$的全图最短路。 |
| $d_u$ |
从源节点$s$到节点$u$的全图最短路的长度。 |
| 当前最短路 |
如果并未考虑图$G$中所有从$s$到$u$的路径，而只考虑了一部分路径，其中最短的那条就是从$s$到$u$的当前最短路。随着算法进行，考虑越来越多的路径，这个当前最短路会变短。 |
| $S$ |
已求出全图最短路的节点的集合。 |
| $Q$ |
优先队列，其元素是边。其中每个元素$(u,v)$满足$u∈S$且$v∉S$。排序权重为$d_v$。 |
《算法导论》中，Dijkstra算法的伪代码如下（我加了一些注释）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
DIJKSTRA(G, w, s)
// s的当前最短路长度是0，其他节点的当前最短路长度是+∞。
INITIALIZE-SINGLE-SOURCE(G, s)
// S是节点集合（V的子集），其中每个节点u都已经求得了全图最短路。
// 初期所有节点都没求得全图最短路。
S ← ∅
// Q是一个节点的优先队列，包含所有尚未求得全图最短路的节点。Q中的节点按照当前最短路的长度从小到大排序。
// 初期所有节点都没求得全图最短路，所以都在Q中。
Q ← V[G]
// 循环直到Q中所有节点都清空（都移动到S），即所有节点都已经求出全图最短路。
while Q ≠ ∅
// 从Q中取出当前最短路长度最小的节点u
// 并认为u的当前最短路就是全图最短路。（这个不是那么显然，后续有说明）
do u ← EXTRACT-MIN(Q)
// 将u放进集合S中，即标注为“已求得u的全图最短路”。
S ← S∪{u}
// 对于u的每个邻接点v
for each vertex v∈Adj[u]
// 更新v的当前最短路。
// 具体策略是：有一个从s到v的新路径，即“从s走全图最短路到u，再从u到v”。
// 这个新路径可能比v的当前最短路长，也可能比v的当前最短路短。（这个不那么显然，后续有说明）
// 如果新路径比v的当前最短路短，就把v的当前最短路替换为这条新路径。
do RELAX(u, v, w)
|
3. C++实现的思路
维持一个优先队列Q，但队列里不是“节点”而是“边”。边(u, v)中u∈S，v∉S。
边在队列中的权值不是边本身的权$w_{u,v}$而是$d_u+ w_{u,v}$，这里$d_u$是节点u的全图最短路长度。
每次选择优先队列中权最小的那条边$(u,v)$（规定$u∈S，v∉S$）：
- 将$v$纳入S，并设置$d_v=d_u+ w_{u,v}$。
- 考察$v$的所有邻接边$(v, p)$中，如果$p∉S$，就将边$(v, p)$纳入Q，权值是$d_v + w_{v,p}$。
4. 可能的疑惑
4.1. 为什么C++中优先队列Q里要保存边而不是保存点
先明确一个设定：优先队列Q中不能保存两个重复的元素。如果优先队列保存节点，则队列中每个节点只会存在一个。
但由于当前最短路是可能变化（变短）的，这就导致已经加入Q的节点的权会变化。但优先队列并不支持对其中单个元素赋新权值，甚至不能将元素先取出队列，修改权值再重新入队，因为优先队列只能从队头出队。
结果就是，除非允许同一个节点多次添加到优先队列中，那么权更小的那次添加将会先出队。
对于节点v的“多次添加”其实就是将边$(p,v)$、$(q,v)$、$(r,v)$、$(u,v)$等等分别添加到Q中。即，Q中保存的是边。
由于每条边只会在起点（假设$(u,v)$中u是起点）刚加入S的时候被添加到Q，这就保证了同一条边不会多次入Q。
4.2. C++中每次只考察新加入Q的节点的邻接边会不会导致遗漏
一个显然的忧虑：
考虑这样一张图，里面只有4个节点s、p、q、v。$d_p$比$d_q$小，但从v的全图最短路是经过q而不是经过p。
1
2
3
4
5
|
graph LR
s --3--> p
p --7--> v
s --6--> q
q --1--> v
|
其中p比q先入S，所以(p,v)入Q时，(q,v)还没入Q。但不用担心s-p-v就直接成为了v的最短路，因为(s-q)的长度比(s-p-v)小，会先出Q；而(s-q)出Q的时候，(s-q-v)自然就入Q了，并抢到了(s-p-v)的前面。
那么，万一(s-q)比(s-p-v)长呢？
这也不用担心。因为如果(s-q)比(s-p-v)长，那么(s-q-v)自然就更比(s-p-v)长了，即v的全图最短路是(s-p-v)，让(s-p-v)先出Q也毫无问题。
4.3. 节点进入S的顺序
节点从Q进入S的顺序是按照节点的全图最短路长度从小到大递增顺序排序的（如果边权不是非负而是恒正，则是严格递增）。
考虑这样一个思想实验：
设想图G中的每条边都是空心玻璃管，和同一节点相邻的边互相连通。
初期所有管子都是空的。从s注入液体，假设液体在所有管中的流动速度都相同。
那么很明显，液体到达各节点的顺序，就是各节点全图最短路长度从小到大的顺序。
5. C++算法实现
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
// 邻接矩阵的紧凑表达
template<typename WEIGHT>
class PairMap {
struct pairHash {
size_t operator()(const pair<int, int> &p) const {
return (static_cast<size_t>(p.first) << 32u) | static_cast<size_t>(p.second);
}
};
// 从节点对到边下标的映射
unordered_map<pair<int, int>, int, pairHash> pair2index;
// 从边下标到边权的映射
vector<WEIGHT> weights;
public:
// n 比最大的节点下标还要大1。
PairMap() {}
// 添加一个pair->value映射。不考虑重复pair的情况。
// u < n, v < n, weights >= 0
void add(int u, int v, const WEIGHT &w) {
if (u > v) {
swap(u, v);
}
this->pair2index[make_pair(u, v)] = this->weights.size();
this->weights.push_back(w);
}
// 查询边下标，如果没有则返回-1。
int getIndex(int u, int v) {
if (u > v) {
swap(u, v);
}
auto ite = this->pair2index.find(make_pair(u, v));
if (ite == this->pair2index.end()) {
return -1;
} else {
return ite->second;
}
}
const WEIGHT &getWeight(int index) {
return this->weights[index];
}
};
// 需要PairMap保存边。
// 调用顺序：
// 1 - Dijkstra(n)
// 2 - addEdge 所有边
// 3 - calc() 执行dijkstra算法。
// 4 - getDistance / getPrev
class Dijkstra {
int nodeCount; // 节点数
// 邻接表
vector<vector<int>> adjacentNodes; // [i]和节点i邻接的节点的下标。
vector<int> distance; // [i]从源到节点i的最短路长度。
vector<int> prev; // [i]从源到节点i的最短路径上，节点i的前一个节点的下标。-1表示没有或不知道前一个节点。
vector<bool> visited; // [i]是否已求出从源到节点i的最短路。也可视为“是否在集合S中”。
// 边
PairMap<int> edges;
public:
// n是节点的数量。
Dijkstra(int n) :
nodeCount(n),
adjacentNodes(n){};
// 添加一条边，0 <= u、v < nodeCount
void addEdge(int u, int v, int weight) {
adjacentNodes[u].push_back(v);
adjacentNodes[v].push_back(u);
edges.add(u, v, weight);
}
// 查询下标为node的节点的邻接节点
const vector<int> &getAdjacent(int node) const {
return adjacentNodes[node];
}
// 计算从节点s开始的单源最短路径。填充distance, prev和visited。
void calc(int s) {
// 边的优先队列
class EdgeInQueue {
public:
int from; // S中的节点
int to; // S外的节点
int weight;
bool operator<(const EdgeInQueue &other) const {
return this->weight > other.weight;
}
};
priority_queue<EdgeInQueue> edgeQueue; // pair<边权, 未进S的节点下标>
// S设成空集
distance.resize(nodeCount, INT_MAX);
prev.resize(nodeCount, -1);
visited.resize(nodeCount, false);
// 开始计算！
// 先将s放入S。
distance[s] = 0; // 从s到s距离自然是0
prev[s] = -1; // 从s到s的话没有前驱结点。
visited[s] = true;
for (auto adjNode : adjacentNodes[s]) {
edgeQueue.push(EdgeInQueue{s, adjNode, edges.getWeight(edges.getIndex(s, adjNode))});
}
while (!edgeQueue.empty()) {
auto e = edgeQueue.top();
edgeQueue.pop();
if (visited[e.to]) {
continue;
}
// 将e.to添加到S中。
distance[e.to] = e.weight;
prev[e.to] = e.from;
visited[e.to] = true;
for (auto adjNode : adjacentNodes[e.to]) {
if (visited[adjNode]) {
continue;
}
edgeQueue.push(EdgeInQueue{
e.to,
adjNode,
distance[e.to] + edges.getWeight(edges.getIndex(e.to, adjNode))
});
}
}
}
// 获取各节点单源最短路的长度。
const vector<int> &getDistance() const {
return this->distance;
}
// 获取各节点单源最短路的上一个节点。
const vector<int> &getPrev() const {
return this->prev;
}
};
|