前言
今天，我们来讲最短路，首先看只有一个起点（单源）的情况。
为了书写方便，我们约定以下内容：
template<class W>
using Graph = vector<vector<pair<int, W>>>; // 邻接表(vector实现)
template<class W>
using AdjMatrix = vector<vector<W>>; // 邻接矩阵
template<class W>
struct Edge{
int u, v;
W w;
};- 图的顶点数记为
，边数记为
。
- 最短路的源点记为
。
- 记
为边
的权值。
- 记
为点
的实际最短路长度。
- 记
为点
，特别地，当最短路算法结束时，
。
Bellman-Ford 算法
Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在（有负环）的情况进行判断。
过程
先介绍松弛操作：对于边，松弛操作对应下式：
这么做很容易理解：尝试用（
取最短路径）去更新
点最短路的长度，如果这条路径更优，就进行更新。
我们不断尝试对图上每一条边进行松弛。每进行一轮循环，就对图上所有的边都松弛一遍，当一次循环中没有成功的松弛操作时，算法停止。
那么，需要循环多少次呢？
如果最短路存在，那么每一次松弛都会让最短路至少加上一条边。而一条简单路径最多只有条边，所以最多松弛
轮就能得到最短路。
如果第轮松弛操作仍然成功，那么说明从
出发，能到达一个负环。
综上，时间复杂度为
判负环的坑点
需要注意的是，跑Bellman-Ford算法时，如果没有给出存在负环的结果，那么只能说明从
所以，如果需要判断图上是否有负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为
的边，然后以超级源点为起点跑 Bellman–Ford。
代码
说明：返回的pair第一个元素表示图是否无负环，第二个元素才是最短路数组。
// edge - 边集
// n - 顶点数
// s - 源点
template<class W>
pair<bool, vector<W>> bellman(const vector<Edge<W>>& edge, int n, int s) {
W inf = numeric_limits<W>::max();
vector<W> dis(n, inf);
dis[s] = 0;
bool flag = false;
for (int i = 0; i < n; i++) {
flag = false;
for (auto e : edge) {
if (dis[e.u] == inf) continue;
if (dis[e.v] > dis[e.u] + e.w) {
dis[e.v] = dis[e.u] + e.w;
flag = true;
}
}
if (!flag) return make_pair(true, dis);
}
return make_pair(false, vector<W>());
}SPFA 算法
即 Shortest Path Faster Algorithm，是对于 Bellman-Ford 的优化。
思路
很多时候，我们不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护哪些结点可能会引起松弛操作，就能只访问必要的边了。
如果要判负环，可以设表示
的最短路经过了多少条边.
当时，说明从
点出发，可以抵达一个负环。
代码
// G - 图
// s - 源点
template<class W>
pair<bool, vector<W>> spfa(const Graph<W>& G, int s) {
int n = G.size();
W inf = numeric_limits<W>::max();
queue<int> q;
vector<W> dis(n, inf);
vector<int> cnt(n, 0);
vector<bool> vis(n, false);
q.push(s);
dis[s] = 0;
vis[s] = true;
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = false;
for (auto [v, w] : G[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return make_pair(false, vector<W>());
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
return make_pair(true, dis);
}Dijkstra 算法
过程
将节点分成两个集合：
- 已确定最短路长度的点集（记为
集合）。
- 未确定最短路长度的点集（记为
集合）。
初始时，所有节点都属于集合。
令，其他点的
为
。
接下来，重复以下操作：
- 从
最小的节点，移到
- 对这个节点的所有出边进行松弛：
。
注意，带负权的图不能使用 Dijkstra 算法。
代码
// G - 图
// s - 源点
template<class W>
vector<W> dijkstra(const Graph<W>& G, int s) {
int n = G.size();
W inf = numeric_limits<W>::max();
vector<W> dis(n, inf);
vector<bool> vis(n, false);
dis[s] = 0;
for (int i = 0; i < n; i++) {
int u = 0;
W mind = inf;
for(int j = 0; j < n; j++)
if (!vis[j] && dis[j] < mind) {
u = j;
mind = dis[j];
}
vis[u] = true;
for (auto [v, w] : G[u]) {
dis[v] = min(dis[v], dis[u] + w);
}
}
return dis;
}优化
上述代码时间复杂度是，能否优化呢？
我们发现，只能优化找最小点的过程。
我们用一个小根堆来维护（按第一关键字）。初始时候插入，计算时，直接从堆顶取出的节点即是最优，然后弹出该节点。
松弛的时候，如果发生改变，那么就插入
。
时间复杂度
代码
template<class W>
vector<W> dijkstra(const Graph<W>& G, int s) {
int n = G.size();
W inf = numeric_limits<W>::max();
priority_queue<pair<W, int>, vector<pair<W, int>>, greater<pair<W, int>>> q;
vector<W> dis(n, inf);
vector<bool> vis(n, false);
dis[s] = 0;
q.emplace(0, s);
while (q.size()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto& [v, w] : G[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.emplace(dis[v], v);
}
}
}
return dis;
}下一次，我们将学习多源最短路。
