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

一、问题引入

在图论中，单源最短路径问题是最基础也最重要的问题之一。Dijkstra算法虽然高效，但它无法处理负权边。Bellman-Ford算法可以处理负权边，但时间复杂度高达O(VE)。

SPFA（Shortest Path Faster Algorithm） 是对Bellman-Ford算法的队列优化版本。它利用一个队列来维护需要松弛的顶点，平均情况下效率接近Dijkstra，同时保留了处理负权边和检测负环的能力。

二、算法原理

2.1 核心思想

SPFA的基本观察是：只有当一个顶点的最短距离被更新时，从它出发的边才可能引起其他顶点的距离更新。因此，我们不需要像Bellman-Ford那样每次都遍历所有边，而是只处理那些”距离发生变化”的顶点。

2.2 算法流程

1. 初始化：源点距离为0，其他点为无穷大
2. 将源点加入队列
3. 从队列中取出一个顶点u
4. 遍历u的所有邻接边，尝试松弛（即更新邻接点的最短距离）
5. 如果某个邻接点v的距离被更新且v不在队列中，将v入队
6. 重复步骤3-5直到队列为空

2.3 负环检测

如果一个顶点被松弛超过V次，说明图中存在负权回路。因为最短路径最多包含V-1条边，超过这个次数就意味着可以无限减小距离。

三、Java代码实现

import java.util.*;

/**
 * SPFA最短路径算法实现
 * 支持负权边和负环检测
 */
public class SPFA {

    // 图的邻接表表示
    private List<List<Edge>> graph;
    private int numVertices;

    /**
     * 边类
     */
    static class Edge {
        int to;      // 目标顶点
        int weight;  // 边权重

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    /**
     * 初始化图
     * @param numVertices 顶点数量
     */
    public SPFA(int numVertices) {
        this.numVertices = numVertices;
        this.graph = new ArrayList<>();
        for (int i = 0; i < numVertices; 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算法求单源最短路径
     * 时间复杂度：平均O(E)，最坏O(VE)
     * 空间复杂度：O(V + E)
     *
     * @param source 源点
     * @return 距离数组，如果存在负环返回null
     */
    public int[] shortestPath(int source) {
        int[] dist = new int[numVertices];
        boolean[] inQueue = new boolean[numVertices];
        int[] count = new int[numVertices]; // 记录每个顶点入队次数

        // 初始化距离
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // 使用LinkedList作为队列
        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 edge : graph.get(u)) {
                int v = edge.to;
                int weight = edge.weight;

                // 松弛操作：如果经过u到v更短，则更新
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;

                    // 如果v不在队列中，将其入队
                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                        count[v]++;

                        // 负环检测：如果某个顶点入队超过V次，存在负环
                        if (count[v] > numVertices) {
                            System.out.println("检测到负权回路！");
                            return null;
                        }
                    }
                }
            }
        }

        return dist;
    }

    /**
     * SPFA算法的SLF优化（Small Label First）
     * 如果待入队顶点的距离小于队首，则插入队首
     */
    public int[] shortestPathSLF(int source) {
        int[] dist = new int[numVertices];
        boolean[] inQueue = new boolean[numVertices];
        int[] count = new int[numVertices];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        Deque<Integer> deque = new LinkedList<>();
        deque.offerFirst(source);
        inQueue[source] = true;
        count[source] = 1;

        while (!deque.isEmpty()) {
            int u = deque.pollFirst();
            inQueue[u] = false;

            for (Edge edge : graph.get(u)) {
                int v = edge.to;
                int weight = edge.weight;

                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;

                    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] > numVertices) {
                            System.out.println("检测到负权回路！");
                            return null;
                        }
                    }
                }
            }
        }

        return dist;
    }

    /**
     * 打印最短路径结果
     */
    public void printResult(int[] dist, int source) {
        if (dist == null) return;

        System.out.println("从顶点 " + source + " 出发的最短距离：");
        for (int i = 0; i < numVertices; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("到顶点 " + i + ": 不可达");
            } else {
                System.out.println("到顶点 " + i + ": " + dist[i]);
            }
        }
    }

    public static void main(String[] args) {
        // 创建一个包含负权边的图
        SPFA spfa = new SPFA(6);

        // 添加边 (from, to, weight)
        spfa.addEdge(0, 1, 5);
        spfa.addEdge(0, 2, 3);
        spfa.addEdge(1, 3, 6);
        spfa.addEdge(1, 2, 2);
        spfa.addEdge(2, 4, 4);
        spfa.addEdge(2, 5, 2);
        spfa.addEdge(2, 3, 7);
        spfa.addEdge(3, 4, -1);  // 负权边
        spfa.addEdge(3, 5, 1);
        spfa.addEdge(4, 5, -2);  // 负权边

        System.out.println("=== 标准SPFA ===");
        int[] dist1 = spfa.shortestPath(0);
        spfa.printResult(dist1, 0);

        System.out.println("\n=== SPFA with SLF优化 ===");
        int[] dist2 = spfa.shortestPathSLF(0);
        spfa.printResult(dist2, 0);

        // 测试负环检测
        System.out.println("\n=== 负环检测测试 ===");
        SPFA negativeCycleGraph = new SPFA(3);
        negativeCycleGraph.addEdge(0, 1, 1);
        negativeCycleGraph.addEdge(1, 2, -3);
        negativeCycleGraph.addEdge(2, 0, 1);  // 0->1->2->0 = -1，负环
        int[] dist3 = negativeCycleGraph.shortestPath(0);
        if (dist3 == null) {
            System.out.println("正确检测到负环！");
        }
    }
}

四、复杂度分析

五、算法优化技巧

1. SLF优化：小距离顶点优先处理，减少无效松弛
2. LLL优化：维护队列中距离的平均值，大于平均值则放队尾
3. 堆优化：使用优先队列替代普通队列，但会丧失处理负权的能力

六、总结

SPFA算法是图论学习中承上启下的关键算法：
– 它比Dijkstra更通用（支持负权边）
– 它比Bellman-Ford更高效（平均情况下）
– 它引入了队列优化的重要思想

掌握SPFA后，读者可以更深入地理解最短路径算法的本质差异，以及不同优化策略对实际性能的影响。