Dijkstra算法用于在所有边权都非负的图上，求单源点最短路。
设
n
n
n是图上结点的数量，
m
m
m是边的数量。则朴素Dijkstra算法的时间复杂度是
O
(
n
2
)
O(n^2)
O(n2)，适合稠密图（点少边多）；堆优化版的Dijkstra算法的时间复杂度是
O
(
m
l
o
g
n
)
O(mlogn)
O(mlogn)，适合稀疏图（点多边少）。
如果是稠密图，那么边的数量
m
m
m和点数的平方
n
2
n^2
n2基本是一个规模的。如果用堆优化版的Dijkstra，那么复杂度就可以视为
O
(
n
2
l
o
g
n
)
O(n^2logn)
O(n2logn)，这个时候是不如朴素版Dijkstra的。
如果是稀疏图，那么边的数量
m
m
m和点的数量
n
n
n基本是一个规模的，题目数据可能给到
1
0
5
10^5
105。如果用朴素版的Dijkstra，那么规模就是
1
0
10
10^{10}
1010了，肯定会超时。
Dijkstra算法属于贪心算法。
1 朴素Dijkstra算法
例如，要求
1
1
1号点到
n
n
n号点的的最短距离。
-
d
i
s
t
[
1
]
=
0
dist[1]=0
dist[1]=0表示到
1
1
1号点自己的距离是
0
0
0，其他的
d
i
s
t
[
i
]
=
+
∞
dist[i] = +\infty
dist[i]=+∞。也就是说初始时只有起点到自己的距离是确定了的，为
0
0
0，到其它点的距离都是没有确定的。
- 集合
S
S
S中存的是当前已经确定最短路的点，
S
S
S初始化为空集。
- 循环
n
−
1
n-1
n−1次，每次找到不在
S
S
S中的距离最小的点（所以第一次循环找到的是源点
1
1
1）
t
t
t，将
t
t
t这个点加入到集合里（说明到
t
t
t的距离就已经确定了）。还要用
t
t
t来更新其它点，也就是说对于每个点
j
j
j，先到
t
t
t的距离
d
i
s
t
[
t
]
dist[t]
dist[t]，加上
j
j
j到
t
t
t的距离
g
[
j
]
[
t
]
g[j][t]
g[j][t]，如果比原来的
d
i
s
t
[
j
]
dist[j]
dist[j]要小，就用这个值来更新
d
i
s
t
[
j
]
dist[j]
dist[j]。
最后，对于任意一个终点
n
n
n，如果
d
i
s
t
[
n
]
dist[n]
dist[n]不是正无穷，就说明从源点
1
1
1到目标点
n
n
n是可达的，最短距离就是
d
i
s
t
[
n
]
dist[n]
dist[n]。
模板题：Dijkstra求最短路 I。
在下面的实现里，因为点的标号是连续的一串属，用布尔数组st来模拟在不在集合
S
S
S里。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
// g存邻接矩阵，dist[j]存从1到j的距离
int g[N][N], dist[N];
// st[j]为true时表示j在S数组里，即已经确定距离
bool st[N];
// 计算结点1到结点n的最短距离
int dijkstra(int n) {
// dist数组也初始化为正无穷，表示没计算过
memset(dist, 0x3f, sizeof dist);
// 到1自己的距离为0
dist[1] = 0;
// 只要循环n-1次，因为每次都会在S外找一个dist最小的
// n-1次之后，S里已经有n-1个元素，如果有第n轮一定直接选到最后那个元素了
// 所以没必要做到n轮，n-1轮之后dist就已经算完了
for (int i = 0; i < n - 1; i ++ ) {
// 在S外（st[j]为false的）找一个最小的dist[t]
int t = -1;
for (int j = 1; j <= n; j ++ ) {
if (!st[j] && (t == -1 || dist[j] < dist[t ]))
t = j;
}
// 将其加入到S中
st[t] = true;
// 用它来更新到其它点的距离，这里不需要判断只更新没确定的
// 因为即使是已经确定的，这样求min的更新也不会破坏它
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
// 如果要求的n号点还是正无穷，那说明不可达
if (dist[n] == 0x3f3f3f3f) return -1;
// 否则dist[n]就是1号点到n号点的距离
return dist[n];
}
int main() {
// 图里每条边都初始化为正无穷，表示不可达
memset(g, 0x3f, sizeof g);
int n, m;
cin >> n >> m;
while (m -- ) {
int x, y, z;
cin >> x >> y >> z;
// 由于有重边，两个结点之间只要记录最短的
// 所以这里取min
g[x][y] = min(g[x][y], z);
}
// 输出从结点1到结点n的最短距离
cout << dijkstra(n) << endl;
return 0;
}
注意，因为朴素Dijkstra用在稠密图上，所以直接存到邻接矩阵里。
还有一个可以优化的地方，如果只想求到
n
n
n的距离
d
i
s
t
[
n
]
dist[n]
dist[n]，那么找到的t==n的时候就可以提前break出来。
2 堆优化Dijkstra算法
如果是稀疏图，题目的结点数
n
n
n很大，使用朴素Dijkstra算法就会超时。
稀疏图，用邻接表存储，然后用堆优化Dijkstra算法来做，下面的分析也是基于邻接表的。注意，邻接表找结点
t
t
t的所有边不需要遍历
n
n
n个点，只要遍历一下
t
t
t位置的链表就行了。
下面看一下在稀疏图里，Dijkstra算法还有哪些可以优化的地方。回顾一下前面朴素Dijkstra算法的过程，循环里有三个操作：
循环n - 1次
找一个结点t，是不在S中的距离最近的点
将t加入到S里
用t更新其它点的距离
第二个操作：将
t
t
t加入到
S
S
S里。
就直接在数组里标记，所以是
O
(
1
)
O(1)
O(1)的。一共循环了
n
−
1
n - 1
n−1次，所以总共的计算量规模就是
n
n
n。
第三个操作：用
t
t
t更新其它点的距离。
实际上是只用到所有从
t
t
t出发的边，而
t
t
t每次都是不一样的点。所以这个操作在
n
−
1
n - 1
n−1次循环里实际是遍历了所有边，所以总共的计算量规模就是
m
m
m。
第一个操作：找一个结点
t
t
t，是不在
S
S
S中的距离最近的点。
每一次都要循环
n
n
n次，在
n
−
1
n - 1
n−1次循环里，总共的计算量规模就是
n
2
n^2
n2。
所以可以发现计算量的瓶颈在第一个操作，而在一堆数里面找一个最小的数，可以直接用小根堆，这样这个操作的时间复杂度可以变成
O
(
1
)
O(1)
O(1)的。在
n
−
1
n - 1
n−1次循环里总共的计算量规模可以下降到
n
n
n。
如果用堆来存了到每个点的距离，那么第三个操作就变成了在堆中修改一个数，在
n
n
n个元素的堆中修改一个元素的时间复杂度是
O
(
l
o
g
n
)
O(logn)
O(logn)，一共要修改边数
m
m
m这么多次，所以这个操作的计算量规模上升到
m
l
o
g
n
mlogn
mlogn。
所以堆优化Dijkstra算法的瓶颈在第三个操作——用
t
t
t更新其它点的距离。这和朴素Dijkstra算法的瓶颈是不一样的。因为这个操作，堆优化Dijkstra算法的时间复杂度就是
O
(
m
l
o
g
n
)
O(mlogn)
O(mlogn)的。
另外， 如果手写模拟堆来做，才能支持修改堆里的任意一个元素，但是手写堆很麻烦。
如果用STL的优先队列来做，因为不支持修改任意一个元素，这里的解决方案就是用冗余。即每次都直接加入新的元素，这样做的话，堆里总共的元素个数要达到
m
m
m个，这样实现的堆优化Dijkstra算法的时间复杂度就变成了
m
l
o
g
m
mlogm
mlogm。
由于
m
<
n
2
m < n^2
m<n2，所以
m
l
o
g
m
<
m
l
o
g
(
n
2
)
<
2
m
l
o
g
n
mlogm < mlog(n^2) < 2mlogn
mlogm<mlog(n2)<2mlogn，它和
m
l
o
g
n
mlogn
mlogn实际也是一个级别的。另外因为是稀疏图，所以
m
m
m实际远比
n
2
n^2
n2小，所以这个常数也比
2
2
2小很多了，就是一点几，这样写方便而且速度也够。
由于这样做的堆里存在很多冗余，所以找到的最小值可能之前已经确定过了，这里就用st数组来判断，如果是已经确定过的，就把它扔掉再重新找就可以了。
模板题：Dijkstra求最短路 II。
在下面的实现里，因为是稀疏图所以选用邻接表来做。用邻接表来做，就不用对重边做特殊的处理了（邻接矩阵时候要取
m
i
n
min
min），因为所有重边都保存下来了，算法就保证了在重边里一定可以拿到最短的来做。
因为pair自动按第一关键字优先来比较大小，所以这里堆里存
{
距
离
,
点
编
号
}
\{距离,点编号\}
{距离,点编号}。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010, M = N;
// 带权w的邻接表
int h[N], e[M], ne[M], idx, w[M];
void add_edge(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++ ;
}
int dist[N];
bool st[N];
int dijkstra(int n) {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 存pair<int, int>的小根堆
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 到1距离为0
heap.push({0, 1});
// 这里不用n-1次这样遍历了，直接遍历到堆空
while (heap.size()) {
// 取出堆顶，就是最小的距离
// 注意这里不能用auto&，因为pop之后这个top()就变了
auto t = heap.top();
heap.pop();
// 但是这个距离可能已经是算过的S里的点的了
int ver = t.second, distance = t.first;
if (st[ver]) continue;
// 至此，说明是S外的点，把它加到S里
st[ver] = true;
// 遍历ver连接的所有边，更新t连接的结点j的dist
for (int i = h[ver]; i != -1; i = ne[i]) {
// 这条边的结点号是j
int j = e[i];
// 更新
if (dist[j] > dist[ver] + w[i]) {
dist[j] = dist[ver] + w[i];
// 如果更新了，还要把它加入到堆里
// 本来应该修改，但是用STL的修改不了，直接加
heap.push({dist[j], j});
}
}
}
// 最后一样的判断n号点距离
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
// 清空邻接表
memset(h, -1, sizeof h);
int n, m;
cin >> n >> m;
while (m -- ) {
int x, y, z;
cin >> x >> y >> z;
// 直接在邻接表里加边
add_edge(x, y, z);
}
cout << dijkstra(n) << endl;
return 0;
}
