每日算法 — 使用java实现SPFA算法：队列优化的最短路径与负环检测

SPFA（Shortest Path Faster Algorithm）是对Bellman-Ford算法的经典优化，利用队列动态维护”距离可能变小的顶点”，避免了对所有边进行无意义的松弛操作。本文用Java完整实现SPFA，并讲解负环检测的核心技巧。

算法思想

Bellman-Ford算法需要对图中所有边进行V-1轮松弛，时间复杂度为O(VE)。SPFA的核心洞察是：只有当一个顶点的最短距离被更新后，从它出发的边才可能影响其他顶点。因此，SPFA使用一个队列，仅将”距离发生变化”的顶点入队，大幅减少无效松弛。

核心步骤

1. 初始化源点距离为0，其余顶点距离为正无穷，源点入队
2. 从队列中取出顶点u，标记为不在队列中
3. 遍历u的所有邻接边(u, v, w)，若dist[u] + w < dist[v]，则更新dist[v]并将v入队（若v不在队列中）
4. 重复步骤2-3直到队列为空

负环检测

若某个顶点入队次数超过V次，说明存在从源点可达的负权回路，最短路径不存在（可以无限缩小）。

完整Java实现

import java.util.*;

/**
 * SPFA算法实现：单源最短路径与负环检测
 * 基于邻接表存储图结构，使用队列优化松弛过程
 */
public class SPFAShortestPath {

    // 边类：存储目标顶点与边权
    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<List<Edge>> graph;          // 邻接表
    private final int INF = Integer.MAX_VALUE / 2; // 避免溢出的大数

    public SPFAShortestPath(int n) {
        this.n = n;
        this.graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
    }

    /**
     * 添加有向边
     * @param from 起点
     * @param to   终点
     * @param weight 边权（可为负数）
     */
    public void addEdge(int from, int to, int weight) {
        graph.get(from).add(new Edge(to, weight));
    }

    /**
     * SPFA核心算法
     * @param source 源点编号
     * @return Result对象，包含最短距离数组和负环标记
     */
    public Result spfa(int source) {
        int[] dist = new int[n];
        boolean[] inQueue = new boolean[n]; // 标记顶点是否在队列中
        int[] count = new int[n];           // 记录各顶点入队次数，用于负环检测
        Arrays.fill(dist, INF);
        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.get(u)) {
                int v = e.to;
                int w = e.weight;

                // 松弛操作：若经过u到达v更短，则更新
                if (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 new Result(dist, true);
                        }
                    }
                }
            }
        }

        return new Result(dist, false);
    }

    /**
     * 获取从源点到目标点的最短路径（需配合SPFA结果使用）
     * 使用BFS/DFS反向追踪前驱节点构建路径
     */
    public List<Integer> getShortestPath(int source, int target) {
        int[] dist = new int[n];
        int[] prev = new int[n]; // 前驱节点数组
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        dist[source] = 0;

        boolean[] inQueue = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        inQueue[source] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;
            for (Edge e : graph.get(u)) {
                int v = e.to;
                if (dist[u] + e.weight < dist[v]) {
                    dist[v] = dist[u] + e.weight;
                    prev[v] = u; // 记录前驱
                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }

        // 反向构建路径
        List<Integer> path = new ArrayList<>();
        if (dist[target] == INF) return path; // 不可达

        for (int at = target; at != -1; at = prev[at]) {
            path.add(at);
        }
        Collections.reverse(path);
        return path;
    }

    // 结果封装类
    static class Result {
        final int[] distances;
        final boolean hasNegativeCycle;
        Result(int[] distances, boolean hasNegativeCycle) {
            this.distances = distances;
            this.hasNegativeCycle = hasNegativeCycle;
        }
    }

    // 测试用例
    public static void main(String[] args) {
        // 示例1：含负权边但无负环的图
        SPFAShortestPath spfa1 = new SPFAShortestPath(5);
        spfa1.addEdge(0, 1, 5);
        spfa1.addEdge(0, 2, 3);
        spfa1.addEdge(1, 3, 2);
        spfa1.addEdge(1, 2, -4);  // 负权边
        spfa1.addEdge(2, 4, 1);
        spfa1.addEdge(3, 4, -3);  // 负权边

        Result res1 = spfa1.spfa(0);
        System.out.println("=== 示例1：含负权边 ===");
        System.out.println("存在负环: " + res1.hasNegativeCycle);
        for (int i = 0; i < 5; i++) {
            System.out.println("到顶点 " + i + " 的最短距离: " +
                (res1.distances[i] == spfa1.INF ? "不可达" : res1.distances[i]));
        }
        List<Integer> path = spfa1.getShortestPath(0, 4);
        System.out.println("0->4 最短路径: " + path);

        // 示例2：含负环的图
        SPFAShortestPath spfa2 = new SPFAShortestPath(3);
        spfa2.addEdge(0, 1, 1);
        spfa2.addEdge(1, 2, -3);
        spfa2.addEdge(2, 0, 1); // 0->1->2->0 总权值为 -1，形成负环

        Result res2 = spfa2.spfa(0);
        System.out.println("\n=== 示例2：含负环 ===");
        System.out.println("存在负环: " + res2.hasNegativeCycle);
    }
}

算法复杂度分析

SPFA在随机稀疏图上表现优异，但在竞赛场景中需注意：存在被精心构造的数据使其退化为O(VE)。对于保证非负权边的场景，Dijkstra仍是更稳妥的选择。

与Dijkstra和Bellman-Ford的对比

优化技巧：SLF与LLL

对于稠密图或特殊构造数据，SPFA可以进一步加速：

• SLF（Small Label First）：若新入队顶点的距离小于队首顶点距离，则插入队首而非队尾
• LLL（Large Label Last）：若队首顶点距离大于当前平均距离，则将其移至队尾

这两种启发式策略在竞赛编程中能有效减少SPFA的退化概率。

应用场景

• 差分约束系统：将约束条件转化为带权有向图，用SPFA判断可行性
• 费用流问题：在最小费用最大流中反复求源点到汇点的最短增广路
• 货币兑换套利：检测汇率图中是否存在套利循环（负环）
• 网络路由优化：动态拓扑下计算最优路径

总结

SPFA通过队列的”惰性松弛”策略，在平均情况下大幅提升了Bellman-Ford的效率。其核心代码简洁易懂，同时具备负环检测能力，是处理含负权边最短路径问题的首选算法之一。理解SPFA的关键在于把握”只有距离被更新的顶点才需要继续松弛”这一核心洞察。