1. 朴素 dijkstra 算法: 稠密图-\(O(n^2)\)
1.1 具体步骤
1.1.0 定义:
- \(v_1\) 为源点, \(v_n\) 为终点
- 对于 \(set\) 集合中的点 \(v_i\), 其所对应的 \(d_i\) 表示从 \(v_1\) 到 \(v_i\) 的最短距离
- \(g_{src, dst}\) 表示从 \(src\) 点到 \(dst\) 点的距离
1.1.1 实现:
- 设置 \(d_i = +\infty (i \in [1, n])\), 且 \(d_1 = 0\), \(set = \varnothing\)
- 令 \(d_i = min(d_1, d_2, d_3, ..., d_n)\), 将 \(d_i\) 所对应的点\(v_i(v_i \not\in set)\) 所对应的点 \(v_i\) 加入到 \(set\) 集合中. 如果目标点 \(v_n\) 被加入到 \(set\) 集合, 则 dijkstra 算法结束, 否则继续第二步
- 根据 \(v_i\) 扩展与 \(v_i\) 直接相连的所有点 \(v_k\) 到源点的距离 \(d_k = min(d_k, d_i + g_{i, k})\), 再继续第一步
1.2 代码
int dist[N]; // dist[i] 表示从源点到 i 点的距离
int g[N][N]; // g[i][j] 表示从 i 点到 j 点的距离
bool st[N]; // st[i] == true 表示 dist[i] 已经是源点到 i 点的最短距离了
int dijkstra() {
memset(dist, 0x3f, sizeof(dist)); // 将所有点到源点的距离初始化为正无穷
dist[1] = 0;
for (int i = 0; i < n; ++ i) {
// 选取所有不在 set 集合中的距离源点最近的点 t, 将其加入 set 集合
int t = -1;
for (int j = 1; j <= n; ++ j)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
// 如果终点已经在 set 集合中, 则 dijkstra 算法结束
if (st[n]) break;
// 尝试更新 t 点所连接的所有的点到源点的距离
for (int j = 1; j <= n; ++ j)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}
1.3 证明
加入 \(set\) 集合的点 \(v_i\), 其所对应的 \(d_i\) 一定是其到源点的最小距离
- 假设对于 \(v_i\), 其 \(d_i\) 不是最小的, 那么其一定会被另一个点 \(v_k\) 更新
- 然而由于 \(v_k\) 在 \(v_i\) 之后被加入 \(set\) 集合, 而图中又没有负权边, 所以 \(d_k \geq d_i\), 故 \(d_k + g_{k, i} \geq d_i\), 即假设不成立, 正确性得证
2. 堆优化 dijkstra 算法: 稀疏图-\(O(mlogn)\)
2.1 代码
int dijkstra() {
memset(dist, 0x3f, sizeof(dist));
priority_queue<PII, vector<PII>, greater<PII>> q; // 小根堆
q.push({dist[1] = 0, 1}); // first 为距离 d, second 为点 v
while (!q.empty()) {
auto t = q.top(); // 取出到源点距离最小的点
q.pop();
int dis = t.first;
int v = t.second;
if (st[v]) continue;
st[v] = true; // 加入到 set 集合
// h[v] 表示 v 点所能到的所有点的链表集合的 head
// e[i] 表示 v 点所能直接到的点
// w[i] 表示 v 点到 e[i] 点的距离
// ne[i] 指向下一个节点
for (int i = h[v]; ~i; i = ne[i])
if (dist[e[i]] > dis + w[i]) {
dist[e[i]] = dis + w[i];
q.push({dist[e[i]], e[i]});
}
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}