最短路问题即，给你一张图，让你求出图中两点的最短距离。
这篇文章会讲解 \(Dijkstra\)、\(Spfa\)、\(Floyd\) 三种算法，让您透彻理解最短路！
题目：
\(Dijkstra\) 通常是用来解决图中一个定点到其余点的最短距离，基本思路是：从中心向外扩展，直到扩展到终点为止。
我们用 \(dist[u]\) 来表示从源点 \(s\) 到 \(u\) 的最短距离。
还需要维护一个状态数组 \(st\)，用于在更新最短距离时，判断当前的点的最短距离是否需要更新（是否已经确定）。
在每一次扩展的过程中，我们要先找到当前未确定的点的集合中找到一个距离最小的点，也就是：
int t = -1; // 距离最短的点的编号
for (int j = 1; j <= n; ++j)
if (!st[j] && (t == -1 || dist[j] < dist[t])) // 判断是否符合条件
t = j;
那么我们就已经确定这个点了，把它的状态更新一下：
st[t] = true;
然后用这个点更新所有未确定点的最短距离
for (int j = 1; j <= n; ++j)
if (!st[i]) // 这句话其实可以不用加，因为我们dijkstra算法的性质已经确定后面确定的点不会再比现在的小了
dist[j] = min(dist[j], dist[t] + g[t][j]);
完整代码：
#include <iostream>
#include <cstring>
#define N 510
using namespace std;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 源点到源点的距离是0
for (int i = 1; i <= n; ++i) {
int t = -1;
for (int j = 1; j <= n; ++j)
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
for (int j = 1; j <= n; ++j) dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[n] == 0x3f3f3f3f) return -1; // 不存在最短路径
return dist[n];
}
int main() {
memset(g, 0x3f, sizeof g);
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c); // 防止重边的情况
}
cout << dijkstra() << '\n';
return 0;
}
此代码时间复杂度为 \(O(n^2)\)。
我们发现，朴素 \(Dijkstra\) 主要就耗时在找 \(t\) 上了；在一组数中找到一个最小值，我们自然可以想到用小根堆（不推荐手写）。
于是我们的代码就可以优化成这样了：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define N 200000
typedef pair<int, int> PII; // 存储距离和节点编号
int n, m;
int h[N], e[N], w[N], ne[N], idx; // 因为是点数较多，所以用邻接表存图
int dist[N];
bool st[N];
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, 1});
while (q.size()) {
auto t = q.top();
q.pop();
int ver = t.second;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[ver] + w[i]) {
dist[j] = dist[ver] + w[i];
q.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra() << '\n';
return 0;
}
剩下的咕咕，明天再写。