最短路系列：Dijkstra 算法
大家好，我是Weekoder!
最短路系列的第二期：Dijkstra 他来啦！
那么废话不多说，让我们直奔主题吧。
Dijkstra 算法的用处
与 floyd 算法不同的，Dijkstra 算法用于求解单源最短路径。顾名思义，单源最短路径就是起点唯一，终点有多个的最短路算法。
Dijkstra 的思想是贪心，而这也将在算法的实现步骤中体现出来。
DIjkstra 算法的思想
Dijkstra 算法是以点为研究对象的最短路算法。我们把图中的点分为两种：黑点和白点。黑点是已经找到最短路的点，白点则相反。一开始所有点都是白点，我们需要将这些点全部染成黑点。用一个 \(vis\) 数组标记，\(vis_i=\text{True}\) 代表 \(i\) 点是黑点，反之则是白点。
我们有一个 \(dis\) 数组，\(dis_i\) 代表从源点到点 \(i\) 的最短路。此时显然有：
\[dis_s=0 \]\(s\) 为起点。
而其余的则设为 INF（\(\infty\)）。又有：
\[dis_i=+\infty(i\ne s) \]我们每次在 \(dis\) 中选取一个最小值并染成黑色，此时这个点的最短路就是确定的了。既然这个点的最短路是确定的，我们就可以利用这个点来松弛其他点。即对于一条边 \(cur\to nxt\)，有：
\[dis_{nxt}=\min(dis_{nxt},dis_{cur}+w),(cur,nxt)\in E \]如此往复，直到所有点染成黑色。
Dijkstra 算法的正确性
刚才说到 Dijkstra 是将所有点染成黑色，每次找 \(dis\) 中最小的值，这就是一个贪心。那这个贪心是正确的吗？为什么最小的 \(dis\) 的最短路就是确定了的呢？因为如果 \(dis_i\) 是最小的，那么就不可能有更小的方案从其他地方过来。比如现在有 \(dis_1,dis_2,dis_3\)，其中 \(dis_1<dis_2<dis_3\)，即 \(dis_1\) 最小，就必然有 \(dis_2+dis_3>dis_1\)。这个时候，\(dis_1\) 是怎么也无法更新的。但如果权值为负，这个贪心就不成立了。比如有两条负边权 \(-2\)
和 \(-3\)，哪怕对于一个最小的 \(-4\)，也可能有 \((-2)+(-3)\le-5\)。还有，Dijkstra 无法跑最长路，因为最长路无法用 Dijkstra 的逻辑实现。
Dijkstra 的实现
根据我们上面的逻辑写即可。这份代码仅能通过P3371。
\(\text{Code:}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
struct Edge {
int to, dis;
};
ll n, m, s, dis[N];
bool vis[N];
vector<Edge> nbr[N];
void dijkstra() {
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
for (int i = 1; i <= n; i++) {
ll minx = 1e18, x;
for (int j = 1; j <= n; j++)
if (!vis[j] && dis[j] < minx)
minx = dis[j], x = j;
vis[x] = 1;
for (Edge nxt : nbr[x]) {
ll to = nxt.to, w = nxt.dis;
dis[to] = min(dis[to], dis[x] + w);
}
}
}
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
nbr[u].emplace_back((Edge){v, w});
}
dijkstra();
for (int i = 1; i <= n; i++)
cout << (dis[i] == 0x3f3f3f3f3f3f3f3f ? (ll)pow(2, 31) - 1 : dis[i]) << " ";
return 0;
}
容易发现，Dijkstra 算法的时间复杂度是 \(\Theta(n\cdot(n+m))\)。在 \(m\) 达到上限 \(n^2\) 的时候，算法的时间复杂度约为 \(\Theta(n^3)\)，还不如 floyd。当然，在绝大多数情况下，朴素 Dijkstra 算法的时间复杂度都大约为 \(\Theta(n^2)\)。
Dijkstra 算法的优化
考虑优化 Dijkstra 的时间复杂度。对于第一层大循环的 \(\Theta(n)\)，是一个个给点染色，无法优化。而对于松弛边的 \(\Theta(m)\)，也是必要的，依然无法优化。那么就只能从寻找 \(dis\) 数组的最小值 \(\Theta(n)\) 的复杂度入手。学过二叉堆的都知道有个东西叫优先队列，可以以 \(\Theta(\log n)\) 的复杂度快速维护序列的最值。那我们也可以借助优先队列维护 \(dis\) 的最小值，于是代码的时间复杂度降为 \(\Theta(n\cdot(\log n+m))\approx\Theta(n\log n)\)。
\(\text{Optimal Code:}\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Edge {
int to, dis;
};
struct node {
int y, w;
bool operator<(const node &x)const {
return w > x.w;
}
};
int n, m, dis[N];
bool vis[N];
vector<Edge> nbr[N];
priority_queue<node> q;
void dijkstra(int s) {
memset(vis, 0, sizeof vis);
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
q.push((node){s, 0});
while (!q.empty()) {
node now = q.top();
q.pop();
int cur = now.y;
if (vis[cur]) continue;
vis[cur] = 1;
for (auto nxt : nbr[cur]) {
int to = nxt.to, w = nxt.dis;
if (dis[to] > dis[cur] + w) {
dis[to] = dis[cur] + w;
q.push((node){to, dis[to]});
}
}
}
}
int main() {
int s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
nbr[u].emplace_back((Edge){v, w});
}
dijkstra(s);
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}
（\(\text{Optimal}\) 意为优化）
这份优化后的代码可以通过P4779。
小结
关于单源最短路径 Dijkstra 算法的介绍就到这里。Dijkstra 算法的时间复杂度其实相当优秀，是最短路算法的首选。在无权图中，优先选择 BFS，而在正权图中，优先选择 Dijkstra。而遇到负权图，我们又该怎么办呢？让我们一起期待下一次的最短路算法！