引言：从Bellman-Ford到SPFA
在图论中，单源最短路径问题是最经典的问题之一。给定一个带权有向图和一个源点，如何求出从该源点到所有其他顶点的最短路径？
- Dijkstra算法使用优先队列，时间复杂度为 $O((V+E)\log V)$，但无法处理负权边。
- Bellman-Ford算法通过 $V-1$ 轮全边松弛，可以处理负权边并检测负环，时间复杂度为 $O(VE)$，但对稀疏图效率较低。
SPFA（Shortest Path Faster Algorithm） 由段凡丁于1994年提出，是Bellman-Ford算法的队列优化版本。其核心洞察是：只有在上一次松弛中被成功更新的顶点，才可能在下一轮松弛中继续影响其邻居。因此，SPFA使用一个队列维护”待松弛”的顶点，避免了对所有边进行无意义的遍历。在平均情况下，SPFA的时间复杂度接近 $O(E)$，远优于Bellman-Ford的最坏 $O(VE)$。
本文将用 Java 完整实现 SPFA 算法，讲解其核心思想、负环检测机制，以及 SLF/LLL 两种常用优化策略。
核心思想：队列优化与惰性松弛
Bellman-Ford的浪费
Bellman-Ford 每轮都遍历全部 $E$ 条边进行松弛。假设顶点 $u$ 的距离估计值 $dist[u]$ 在本轮未发生变化，那么从 $u$ 出发的边 $(u,v)$ 的松弛操作 $dist[v] = \min(dist[v], dist[u] + w(u,v))$ 必然不会成功——因为 $dist[u]$ 没变，$dist[v]$ 也不会因此变小。
SPFA的改进
SPFA 维护一个队列 $Q$，初始时仅将源点入队。每次从队首取出顶点 $u$，遍历其所有出边 $(u,v)$：
- 若 $dist[u] + w(u,v) < dist[v]$，则更新 $dist[v]$。
- 如果 $v$ 不在队列中，将 $v$ 入队。
这样，只有真正可能引发更新的顶点才会被处理。对于随机稀疏图，SPFA的平均性能非常优秀。
负环检测
若图中存在从源点可达的负环，则最短路径不存在（可以无限绕环使路径长度趋于 $-\infty$）。SPFA 检测负环的经典方法是计数法：
- 记录每个顶点入队的次数。
- 若某顶点入队次数超过 $V$ 次，则说明存在负环。
原理：在无负环的图中，每个顶点的最短路径最多由 $V-1$ 条边组成，因此每个顶点最多被成功松弛 $V-1$ 次。超过 $V$ 次意味着绕了环，且路径仍在缩短，即存在负环。
Java 完整实现
import java.util.*;
/**
* SPFA 算法完整实现
* 包含：基础最短路径、负环检测（计数法）、SLF与LLL优化
* 时间复杂度：平均 O(E)，最坏 O(VE)
*/
public class SPFA {
/**
* 图的边结构
*/
static class Edge {
int to; // 目标顶点
int weight; // 边权
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
private final int n; // 顶点数
private final List<Edge>[] graph; // 邻接表
private final int[] dist; // 距离数组
private final int[] count; // 入队次数（用于负环检测）
private final boolean[] inQueue; // 是否在队列中
/**
* 构造SPFA求解器
* @param n 顶点数（编号从0到n-1）
*/
@SuppressWarnings("unchecked")
public SPFA(int n) {
this.n = n;
this.graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
this.dist = new int[n];
this.count = new int[n];
this.inQueue = new boolean[n];
}
/**
* 添加有向边
* @param from 起点
* @param to 终点
* @param weight 边权（可为负数）
*/
public void addEdge(int from, int to, int weight) {
graph[from].add(new Edge(to, weight));
}
/**
* 基础SPFA：求单源最短路径
* @param source 源点
* @return 若存在从源点可达的负环，返回null；否则返回距离数组
*/
public int[] shortestPath(int source) {
// 初始化
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(count, 0);
Arrays.fill(inQueue, false);
dist[source] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(source);
inQueue[source] = true;
count[source] = 1;
while (!queue.isEmpty()) {
int u = queue.poll();
inQueue[u] = false;
// 遍历u的所有出边
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
// 松弛操作：若通过u到v更短，则更新
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
// 如果v不在队列中，入队
if (!inQueue[v]) {
queue.offer(v);
inQueue[v] = true;
count[v]++;
// 负环检测：入队次数超过n次
if (count[v] > n) {
return null; // 存在负环
}
}
}
}
}
return dist;
}
/**
* SPFA + SLF优化（Small Label First）
* 思想：若待入队顶点的距离比队首小，则插入队首而非队尾
* 效果：让距离较小的顶点优先处理，加速收敛
* @param source 源点
* @return 若存在负环返回null，否则返回距离数组
*/
public int[] shortestPathSLF(int source) {
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(count, 0);
Arrays.fill(inQueue, false);
dist[source] = 0;
Deque<Integer> deque = new LinkedList<>();
deque.offerLast(source);
inQueue[source] = true;
count[source] = 1;
while (!deque.isEmpty()) {
int u = deque.pollFirst();
inQueue[u] = false;
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) {
// SLF优化：与队首比较，决定插入位置
if (!deque.isEmpty() && dist[v] < dist[deque.peekFirst()]) {
deque.offerFirst(v);
} else {
deque.offerLast(v);
}
inQueue[v] = true;
count[v]++;
if (count[v] > n) {
return null;
}
}
}
}
}
return dist;
}
/**
* SPFA + SLF + LLL优化（Large Label Last）
* SLF：小距离优先（插入队首）
* LLL：大距离后移（若队首距离大于平均值，移到队尾）
* @param source 源点
* @return 若存在负环返回null，否则返回距离数组
*/
public int[] shortestPathSLF_LLL(int source) {
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(count, 0);
Arrays.fill(inQueue, false);
dist[source] = 0;
Deque<Integer> deque = new LinkedList<>();
deque.offerLast(source);
inQueue[source] = true;
count[source] = 1;
long sumDist = 0; // 队列中顶点距离之和，用于LLL的均值计算
int queueSize = 1;
sumDist += dist[source];
while (!deque.isEmpty()) {
// LLL优化：若队首距离大于平均值，移到队尾
while (!deque.isEmpty() &&
dist[deque.peekFirst()] * queueSize > sumDist) {
int moved = deque.pollFirst();
deque.offerLast(moved);
}
int u = deque.pollFirst();
inQueue[u] = false;
sumDist -= dist[u];
queueSize--;
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) {
if (!deque.isEmpty() && dist[v] < dist[deque.peekFirst()]) {
deque.offerFirst(v);
} else {
deque.offerLast(v);
}
inQueue[v] = true;
count[v]++;
sumDist += dist[v];
queueSize++;
if (count[v] > n) {
return null;
}
}
}
}
}
return dist;
}
/**
* 获取具体的最短路径（前驱数组回溯）
* @param source 源点
* @return Pair<距离数组, 前驱数组>；若存在负环返回null
*/
public Result shortestPathWithPredecessor(int source) {
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(count, 0);
Arrays.fill(inQueue, false);
int[] pre = new int[n];
Arrays.fill(pre, -1);
dist[source] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(source);
inQueue[source] = true;
count[source] = 1;
while (!queue.isEmpty()) {
int u = queue.poll();
inQueue[u] = false;
for (Edge e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pre[v] = u; // 记录前驱
if (!inQueue[v]) {
queue.offer(v);
inQueue[v] = true;
count[v]++;
if (count[v] > n) {
return null;
}
}
}
}
}
return new Result(dist.clone(), pre);
}
static class Result {
int[] dist;
int[] pre;
Result(int[] dist, int[] pre) {
this.dist = dist;
this.pre = pre;
}
/**
* 重建从source到target的最短路径
*/
List<Integer> getPath(int source, int target) {
List<Integer> path = new ArrayList<>();
if (pre[target] == -1 && target != source) {
return path; // 不可达
}
int cur = target;
while (cur != -1) {
path.add(cur);
cur = pre[cur];
}
Collections.reverse(path);
return path;
}
}
// ==================== 主程序与测试 ====================
public static void main(String[] args) {
System.out.println("===== 示例1：基础SPFA（含负权边） =====");
SPFA spfa1 = new SPFA(5);
spfa1.addEdge(0, 1, 6);
spfa1.addEdge(0, 2, 7);
spfa1.addEdge(1, 2, 8);
spfa1.addEdge(1, 3, 5);
spfa1.addEdge(1, 4, -4); // 负权边
spfa1.addEdge(2, 3, -3); // 负权边
spfa1.addEdge(2, 4, 9);
spfa1.addEdge(3, 1, -2); // 负权边
spfa1.addEdge(4, 0, 2);
spfa1.addEdge(4, 3, 7);
int[] dist1 = spfa1.shortestPath(0);
System.out.println("从顶点0出发的最短距离：");
for (int i = 0; i < 5; i++) {
System.out.printf(" 到顶点%d: %d%n", i, dist1[i]);
}
// 期望：0->0, 1->2(0->2->3->1), 2->7, 3->4, 4->-2
System.out.println("\n===== 示例2：负环检测 =====");
SPFA spfa2 = new SPFA(3);
spfa2.addEdge(0, 1, 1);
spfa2.addEdge(1, 2, -3);
spfa2.addEdge(2, 0, 1); // 0->1->2->0 的环权值为 -1，是负环
int[] dist2 = spfa2.shortestPath(0);
if (dist2 == null) {
System.out.println("检测到负环！最短路径不存在。");
} else {
System.out.println("无负环，距离：" + Arrays.toString(dist2));
}
System.out.println("\n===== 示例3：路径重建 =====");
SPFA spfa3 = new SPFA(5);
spfa3.addEdge(0, 1, 10);
spfa3.addEdge(0, 2, 3);
spfa3.addEdge(1, 3, 2);
spfa3.addEdge(2, 1, 4);
spfa3.addEdge(2, 3, 8);
spfa3.addEdge(2, 4, 2);
spfa3.addEdge(3, 4, 5);
spfa3.addEdge(4, 3, 7);
Result res = spfa3.shortestPathWithPredecessor(0);
System.out.println("距离数组：" + Arrays.toString(res.dist));
for (int i = 0; i < 5; i++) {
List<Integer> path = res.getPath(0, i);
System.out.printf(" 到顶点%d的路径: %s (长度=%d)%n", i, path, res.dist[i]);
}
System.out.println("\n===== 示例4：三种版本性能对比 =====");
int scale = 1000;
int edges = 5000;
SPFA spfaBase = new SPFA(scale);
SPFA spfaSLF = new SPFA(scale);
SPFA spfaLLL = new SPFA(scale);
Random rand = new Random(42);
for (int i = 0; i < edges; i++) {
int u = rand.nextInt(scale);
int v = rand.nextInt(scale);
int w = rand.nextInt(200) - 50; // -50 ~ 149
if (u != v) {
spfaBase.addEdge(u, v, w);
spfaSLF.addEdge(u, v, w);
spfaLLL.addEdge(u, v, w);
}
}
long t1 = System.nanoTime();
spfaBase.shortestPath(0);
long t2 = System.nanoTime();
spfaSLF.shortestPathSLF(0);
long t3 = System.nanoTime();
spfaLLL.shortestPathSLF_LLL(0);
long t4 = System.nanoTime();
System.out.printf("基础SPFA: %.3f ms%n", (t2 - t1) / 1_000_000.0);
System.out.printf("SPFA+SLF: %.3f ms%n", (t3 - t2) / 1_000_000.0);
System.out.printf("SPFA+SLF+LLL: %.3f ms%n", (t4 - t3) / 1_000_000.0);
}
}
复杂度分析
| 版本 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|---|
| 基础SPFA | $O(E)$ | $O(VE)$ | $O(V)$ | 适合随机稀疏图 |
| SPFA + SLF | $O(E)$ | $O(VE)$ | $O(V)$ | 小距离优先，常数优化明显 |
| SPFA + SLF + LLL | $O(E)$ | $O(VE)$ | $O(V)$ | 双重启发，最坏情况略优 |
| Bellman-Ford | $O(VE)$ | $O(VE)$ | $O(V)$ | 无条件遍历全边 |
| Dijkstra | $O((V+E)\log V)$ | $O((V+E)\log V)$ | $O(V)$ | 不支持负权边 |
注意：SPFA 的最坏复杂度与 Bellman-Ford 相同。在特定构造的数据（如网格图、菊花图）上，SPFA 可能退化。对于保证无负边且需要严格复杂度上界的场景，Dijkstra 仍是首选；若需要处理负边且无负环，SPFA 在实践中的表现通常优于 Bellman-Ford。
SLF与LLL优化详解
SLF（Small Label First）
当顶点 $v$ 需要入队时，比较 $dist[v]$ 与队首顶点的距离：
– 若 $dist[v]$ 更小，插入队首；否则插入队尾。
直觉：距离小的顶点更有可能引发更多有效的松弛，优先处理它们可以加速整个算法的收敛。
LLL（Large Label Last）
在取出队首顶点之前，若队首顶点的距离大于队列中所有顶点距离的平均值，则将其移到队尾，重复此过程直到条件不满足。
直觉：避免处理”过时的”大距离顶点——它们可能已经被更优路径更新，但仍在队列前端阻塞更有希望的顶点。
经典应用场景
差分约束系统
SPFA 是求解差分约束系统的标准工具。给定一组形如 $x_i – x_j \leq c_k$ 的不等式，可以将其转化为图中边 $j \to i$（权值 $c_k$），然后添加超级源点向所有变量连权值为0的边，运行 SPFA 即可求得一组可行解。若检测到负环，则约束系统无解。
网络流费用计算
在最小费用最大流算法中，每次增广都需要在残量网络上求一次单源最短路径。由于残量网络中存在反向边（负权），SPFA 常被用于此步骤。若结合势函数（Johnson技巧），也可将问题转化为非负权图后用 Dijkstra 求解。
总结
通过本文你掌握了：
- SPFA 的核心思想：利用队列实现惰性松弛，避免 Bellman-Ford 的全边盲目遍历
- 完整的 Java 实现，包含基础版本、SLF 优化、LLL 优化及路径重建
- 负环检测的计数法原理与代码实现
- 时间复杂度分析与各算法的适用场景对比
- SPFA 在差分约束系统和网络流中的典型应用
SPFA 的优雅之处在于它用极简单的数据结构（一个普通队列）实现了对 Bellman-Ford 的大幅优化。理解它”只做必要工作”的设计哲学，对培养算法直觉大有裨益。
