外观
19 - 最短路径算法:BFS、Dijkstra 与负权边
前置阅读:17 - 图的 DFS 与 BFS、09 - Top K 与堆。
若权重代表实时延迟或拥塞,静态最短路只是一次快照,不能直接当成长期路由策略。
摘要
从服务 A 到服务 B,经过的服务最少,是否就代表总延迟最低?不一定:一次慢调用可能比两次快调用更耗时。最短路径要先明确每条边的成本,再寻找总成本最小的路线。
本文先建立带权图模型,解释 BFS、Dijkstra 和 Bellman-Ford 各自适用的条件,再通过 Java 示例观察距离如何更新,最后讨论路径恢复与工程边界。
1. 先看边权
把服务或位置表示为节点,把允许的一步调用或移动表示为边。边上的数值称为边权,可以表示延迟或费用。这里假设一条路径的成本等于沿途边权之和,并且一次计算期间边权固定;真实调用中的并行、重试等行为未必满足这个模型。
单源最短路径是从同一个起点(源点)出发,计算到各节点的最小总成本。下文用 V 表示节点数、E 表示边数。代码按有向图处理,u -> v 不表示可以反向走;无向图需在两个方向各保存一条边。
| 图条件 | 常用算法 |
|---|---|
| 所有边等权且非负 | BFS |
| 权重只有 0/1 | 0-1 BFS |
| 非负权重 | Dijkstra |
| 允许负权边 | Bellman-Ford |
| 存在可达负环 | 最短路径可能无定义 |
BFS(广度优先搜索)按经过的边数分层。所有边权都是同一个正数时,总成本就是“跳数 × 单边成本”,因此最少跳数也给出最低成本;所有边权为 0 时,任意可达路径的成本都为 0。边权不同后,跳数就不能代表成本,必须比较累计距离。
负环是总边权小于 0 的环。若源点能到达这个环,并且能从环到达目标,就可以反复绕环,让到目标的成本不断降低,因此该目标没有有限的最短距离。其他不受该环影响的节点仍可能有最短距离。
2. 松弛操作
dist[v] 保存目前找到的、从源点到 v 的最小成本,它在搜索过程中还不一定是最终答案。初始化时源点距离为 0,其他节点为无穷大,表示尚未找到路线。
若 u 已可达,经过边 u -> v 的候选距离就是 dist[u] + w(u,v)。候选值小于 dist[v] 时,说明找到了一条更便宜的路线,应更新 v:
text
dist[v] = min(dist[v], dist[u] + weight)这叫 Relaxation(松弛),即用新路线改善当前距离。例如,到 u 的距离为 3,u -> v 的权重为 2,而 dist[v] 为 8,松弛后就变成 5。不同算法共享这一步,区别在于按什么顺序、重复多少次处理边。
3. Dijkstra 实现
Dijkstra 用优先队列每次取出当前候选距离最小的节点。小顶堆是一种实现优先队列的数据结构,堆顶始终保存最小项。它与 BFS 的普通队列不同:决定处理顺序的是累计成本,而不是入队先后。
为什么此时能确定最短距离?假设已经确定的节点距离都正确,若当前最小候选节点还存在更短路线,沿该路线找到第一个尚未确定的节点,它的前驱已经处理过,因此它必然已有一个候选距离。非负边意味着路线后半段不会降低成本,所以这个候选距离也应小于当前队列最小值,产生矛盾。负权边会使这一步推理失效。
下面是方法片段,需要放入类中并导入 java.util.List。graph 是邻接表,graph.get(u) 保存从 u 出发的边;节点编号、源点和集合引用须合法,所有边权须非负。代码只在扫描到边时检查负权,因此不会检查源点不可达部分的边。
java
record Edge(int to, long weight) {}
record State(int node, long distance) {}
static long[] dijkstra(int source, List<List<Edge>> graph) {
long[] dist = new long[graph.size()];
java.util.Arrays.fill(dist, Long.MAX_VALUE);
dist[source] = 0;
var queue = new java.util.PriorityQueue<State>(
java.util.Comparator.comparingLong(State::distance)
);
queue.offer(new State(source, 0));
while (!queue.isEmpty()) {
State state = queue.poll();
if (state.distance() != dist[state.node()]) continue; // 跳过旧状态
for (Edge edge : graph.get(state.node())) {
if (edge.weight() < 0) throw new IllegalArgumentException(
"negative edge"
);
if (state.distance() > Long.MAX_VALUE - edge.weight()) {
throw new ArithmeticException("distance overflow");
}
long candidate = state.distance() + edge.weight();
if (candidate < dist[edge.to()]) {
dist[edge.to()] = candidate;
queue.offer(new State(edge.to(), candidate));
}
}
}
return dist;
}同一节点可能多次入队:先发现成本为 8 的路线,之后又改进为 5,就会同时留下 (节点, 8) 和 (节点, 5) 两条状态。这里不修改堆内的旧记录,而是在出队时比较状态距离与 dist,不一致就跳过。状态中的距离是入队时的快照,dist 才是当前记录。
邻接表加二叉堆的复杂度常写作 O((V+E) log V)。本文保留旧状态、重新入队的实现,队列最坏可能保存 O(E) 条记录;按队列规模分析,时间上界为 O(V + E log(E+1)),辅助空间为 O(V+E)。对没有平行边的简单图,E 至多为 O(V²),可得到前面的常用时间表达式。这是复杂度推导,不是性能测量。
若边权只有 0 和 1,可以用双端队列(两端都能插入和取出的队列)执行 0-1 BFS:松弛成功后,经过权重 0 的边得到的节点放队首,经过权重 1 的边得到的节点放队尾。前者距离没有增加,应先处理;后者距离增加 1,留到后面处理。正确维护距离与队列顺序时,时间为 O(V+E),无需通用优先队列。本文不展开其实现。
4. 为什么不能有负权边
Dijkstra 的“确定”是指之后不再需要改善这个距离,属于贪心选择:当前做出的选择不必回退。例如有边 s -> a(2)、s -> b(5)、b -> a(-4),按当前最小值先确定 a 为 2,但经 b 到达 a 的成本其实为 1。本文实现直接拒绝负权输入,不能用来处理这种图。
Bellman-Ford 不依赖这个确定顺序,而是对所有边重复松弛。在没有源点可达负环的前提下,最短路线可以去掉不会降低成本的环,得到不重复节点的简单路径,最多包含 V-1 条边。每轮扫描至少能把正确距离沿路径再推进一条边,因此 V-1 轮足够;某轮没有更新时可以提前停止。
再扫描一轮,如果源点可达的边仍能改善距离,就说明存在源点可达负环。下面的实现对此直接抛出异常,并不返回哪些目标受负环影响。Bellman-Ford 的最坏时间为 O(VE);允许负权边不等于遇到负环也能给出有限最短距离。
5. 完整可运行示例:Dijkstra 与 Bellman-Ford
下面的完整类对应文件名 ShortestPathDemo.java,使用 Java 标准集合,无外部依赖。代码使用 record,按正式语言特性需要 Java 16 或更高版本。
输入要求 n > 0,节点编号为 0 到 n - 1,源点合法,边列表及元素不是空引用。完整示例的 Dijkstra 在建图时检查全部边,和第 3 节只检查扫描到的边有所区别。main 只比较一张非负权图的结果,没有覆盖负权、负环或溢出等边界。
距离数组用 Long.MAX_VALUE 表示不可达。因此有效有限距离必须小于这个值;恰好等于它的距离无法与不可达区分。Dijkstra 在每次加法前检查上溢,但 Bellman-Ford 未检查有限距离相加的上溢或下溢,使用它时必须保证所有参与比较的和都在 long 范围内,否则距离和负环检测都可能失真。这里保留原代码行为。
java
import java.util.*;
/**
* 可运行示例:最短路径算法:BFS、Dijkstra 与负权边。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class ShortestPathDemo {
record Edge(int from, int to, long weight) {}
record State(int node, long distance) {}
static long[] dijkstra(int n, List<Edge> edges, int source) {
List<List<Edge>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (Edge e : edges) {
if (e.weight() < 0) throw new IllegalArgumentException("negative edge");
g.get(e.from()).add(e);
}
long[] d = new long[n];
Arrays.fill(d, Long.MAX_VALUE);
d[source] = 0;
PriorityQueue<State> q = new PriorityQueue<>(
Comparator.comparingLong(State::distance)
);
q.offer(new State(source, 0));
while (!q.isEmpty()) {
State s = q.poll();
// 同一节点可能因距离改善多次入队,只处理最新状态。
if (s.distance() != d[s.node()]) continue;
for (Edge e : g.get(s.node())) {
if (s.distance() > Long.MAX_VALUE - e.weight()) {
throw new ArithmeticException("distance overflow");
}
long nd = s.distance() + e.weight();
// 松弛:经过当前节点能得到更短路径时才更新。
if (nd < d[e.to()]) {
d[e.to()] = nd;
q.offer(new State(e.to(), nd));
}
}
}
return d;
}
static long[] bellmanFord(int n, List<Edge> edges, int source) {
long[] d = new long[n];
Arrays.fill(d, Long.MAX_VALUE);
d[source] = 0;
for (int i = 1; i < n; i++) {
boolean changed = false;
// 最短简单路径最多含 V-1 条边,因此最多执行 V-1 轮。
for (Edge e : edges)
if (
d[e.from()] != Long.MAX_VALUE && d[e.from()] + e.weight() < d[e.to()]
) {
d[e.to()] = d[e.from()] + e.weight();
changed = true;
}
if (!changed) break;
}
// 额外一轮仍能松弛,说明存在源点可达的负权环。
for (Edge e : edges)
if (
d[e.from()] != Long.MAX_VALUE && d[e.from()] + e.weight() < d[e.to()]
) throw new IllegalStateException("negative cycle");
return d;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
List<Edge> edges = List.of(
new Edge(0, 1, 4),
new Edge(0, 2, 1),
new Edge(2, 1, 2),
new Edge(1, 3, 1),
new Edge(2, 3, 5)
);
System.out.println(Arrays.toString(dijkstra(4, edges, 0)));
System.out.println(Arrays.toString(bellmanFord(4, edges, 0)));
}
}Dijkstra 手工推演
完整示例的边为 0→1(4)、0→2(1)、2→1(2)、1→3(1)、2→3(5)。括号表示边权,∞ 表示尚不可达。距离数组依次变化如下:
| 处理节点 | 松弛后的距离 | 原因 |
|---|---|---|
| 0 | [0, 4, 1, ∞] | 发现到 1、2 的直接路线 |
| 2 | [0, 3, 1, 6] | 到 1 的成本降为 1+2,到 3 的成本为 1+5 |
| 1 | [0, 3, 1, 4] | 到 3 的成本降为 3+1 |
| 3 | [0, 3, 1, 4] | 没有出边,距离不变 |
节点 1 的旧距离 4 和节点 3 的旧距离 6 后续出队时会被跳过。Bellman-Ford 对同一图重复扫描边,也会得到相同距离。因此,两行预期输出均为 [0, 3, 1, 4]。这是手工推演,并非实测;相同优先级状态的出队顺序不影响这里的距离结果。
6. 路径恢复
前驱是当前最优路线中紧挨着目标节点之前的节点。每次松弛成功、更新 dist[v] 时,同时保存 previous[v] = u。先将前驱初始化为未设置的标记,目标可达且最短距离有定义时,从目标沿前驱回到源点,再反转节点列表,就能恢复路线。
例如,示例中到 3 的前驱链为 3 <- 1 <- 2 <- 0,反转得到 [0, 2, 1, 3],总成本为 1+2+1=4。源点等于目标时返回只包含源点的路径;目标不可达时不要回溯。本文代码只返回距离,尚未实现前驱记录。
有多条等成本路线时,距离相同不代表节点序列相同。只在严格改善距离时更新前驱,可以保留先找到的路线;若有平行边且需要输出具体边,还应记录边的标识,而不只是前驱节点。
7. 静态最短路的工程边界
- 权重若随实时流量、失败率或时间变化,计算结果可能很快过期;
- 多条等成本最短路径用于实际路由时,可约定稳定的平局选择规则(tie-break),例如按节点编号选择,减少因遍历顺序变化导致的路线切换;本文比较器只比较距离,没有约定路线的平局规则;
- A* 使用启发函数估计从当前节点到目标的剩余成本,可能减少搜索范围;它保证最优所需的条件取决于是否允许重新打开已处理节点等实现细节,不能仅凭“估计看起来可靠”就认定答案最优;
- 大图可能无法整体装入内存,需要分区、预计算或专用图存储;
- “延迟最小”不一定等于“系统风险最低”,还可能需要容量、故障域和费用约束。
8. 验证与排障
- 在无溢出的非负权小图上,与 Bellman-Ford 或简单路径枚举做差分测试,即对相同输入比较距离结果;
- 覆盖不可达、零权、重复边、负权和可达负环;
- 检查距离加法溢出,不能只避免对
MAX_VALUE加权; - 若另行实现路径恢复,检查首尾、每条边的方向及合法性,再累加边权,确认等于报告距离;多条最短路径时无需强求节点序列相同;
- 性能异常时记录顶点、边、优先队列峰值和旧状态跳过数量。
9. 容易踩的坑
- 把 BFS 用在不同权重边上。
- Dijkstra 忘记跳过优先队列中的旧状态。
- 以为使用
long或跳过MAX_VALUE就不会溢出;有限距离相加同样可能超出范围,具体实现限制见第 5 节。 - 图不可达时仍恢复路径。
- 实际权重随时间变化,却使用静态最短路模型。
10. 总结
最短路径算法的选择首先由边权约束决定,不能只看题目里有没有“最短”两个字。
- 非负等权图用 BFS,非负权图可用 Dijkstra;存在负权边时可考虑 Bellman-Ford,并处理可达负环。
- 负权边会破坏 Dijkstra 的贪心确定性。
- 需要可解释路径时必须保存前驱,而不只是距离。
Dijkstra 的正确性依赖贪心确定性,继续阅读贪心算法与正确性证明;状态转移视角可对比动态规划。