详解SPFA算法-单源最短路径求解

当图中存在负权边但无负权回路时，Dijkstra算法不再适用，而Bellman-Ford算法虽能处理却效率较低。SPFA（Shortest Path Faster Algorithm）算法作为Bellman-Ford的优化版本，通过队列筛选待更新节点，大幅提升了求解效率，在通信网络路由规划、交通路径优化等场景中被广泛应用。

一、SPFA算法基础概念

1.1 算法定位

SPFA算法是针对单源最短路径问题的优化算法，适用于含负权边但无负权回路的有向图或无向图。它基于Bellman-Ford算法的“松弛”思想，通过引入队列存储待松弛的节点，避免了Bellman-Ford算法中对所有节点的重复检查，从而降低时间复杂度。

1.2 核心思想

SPFA算法的核心是“只对可能更新最短路径的节点进行松弛操作”。具体来说：

• 用一个队列记录当前需要进行松弛操作的节点。
• 每次从队列中取出一个节点，对其所有邻接节点进行松弛（即尝试更新邻接节点的最短路径）。
• 若邻接节点的最短路径被更新且未在队列中，则将其加入队列，等待后续松弛。
• 通过这种方式，避免对不可能更新最短路径的节点进行无效处理。
  

1.3 负权回路检测

SPFA算法还能检测图中是否存在从起点可达的负权回路（即路径总权重为负的环）。若一个节点被加入队列的次数超过图中节点总数，则说明存在负权回路（因为正常情况下，每个节点的最短路径最多被更新n-1次，n为节点数）。

二、SPFA算法的实现步骤

2.1 初始化

• 设起点为s，初始化距离数组dist，dist[s] = 0，其他节点dist[i] = +∞（表示初始时不可达）。
• 初始化队列，将起点s加入队列。
• 初始化入队次数数组cnt，记录每个节点被加入队列的次数，初始均为0，cnt[s] = 1。

2.2 队列循环

• 若队列为空，算法结束（已找到所有可达节点的最短路径）。
• 从队列中取出一个节点u。
• 遍历u的所有邻接节点v，设边u->v的权重为w：
  • 若dist[v] > dist[u] + w（即通过u到v的路径更短）：
    • 更新dist[v] = dist[u] + w。
    • 若v不在队列中：
      • 将v加入队列。
      • cnt[v] += 1，若cnt[v] > n（n为节点数），说明存在负权回路，算法终止。

2.3 结果输出

• 算法结束后，dist数组中存储的就是从起点到各节点的最短路径长度（若仍为+∞，则表示不可达）。
• 若检测到负权回路，输出“存在负权回路”。

三、Java代码实现

以下是基于邻接表的SPFA算法实现，包含最短路径求解和负权回路检测功能：

import java.util.*;

public class SPFAAlgorithm {
    // 邻接表：adj[u]存储所有(u, v, w)，表示u到v的边权重为w
    private List<List<int[]>> adj;
    private int n; // 节点数

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

    // 添加边：u -> v，权重为w
    public void addEdge(int u, int v, int w) {
        adj.get(u).add(new int[]{v, w});
    }

    /**
     * 求解从起点s到所有节点的最短路径
     * @param s 起点
     * @return 距离数组dist，若存在负权回路则返回null
     */
    public int[] spfa(int s) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);

        boolean[] inQueue = new boolean[n]; // 标记节点是否在队列中
        inQueue[s] = true;

        int[] cnt = new int[n]; // 记录节点入队次数
        cnt[s] = 1;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            // 遍历u的所有邻接节点
            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int w = edge[1];

                // 松弛操作：尝试更新v的最短路径
                if (dist[u] != Integer.MAX_VALUE && dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;

                    if (!inQueue[v]) {
                        queue.add(v);
                        inQueue[v] = true;
                        cnt[v]++;

                        // 检测负权回路
                        if (cnt[v] > n) {
                            System.out.println("图中存在从起点可达的负权回路");
                            return null;
                        }
                    }
                }
            }
        }

        return dist;
    }

    // 测试
    public static void main(String[] args) {
        // 示例1：无负权回路的图
        int n1 = 5;
        SPFAAlgorithm graph1 = new SPFAAlgorithm(n1);
        graph1.addEdge(0, 1, 2);
        graph1.addEdge(0, 2, 3);
        graph1.addEdge(1, 2, 1);
        graph1.addEdge(1, 3, 1);
        graph1.addEdge(2, 4, 2);
        graph1.addEdge(3, 4, 4);

        int[] dist1 = graph1.spfa(0);
        if (dist1 != null) {
            System.out.println("示例1（无负权回路）的最短路径：");
            for (int i = 0; i < n1; i++) {
                System.out.println("从0到" + i + "的最短距离：" + (dist1[i] == Integer.MAX_VALUE ? "不可达" : dist1[i]));
            }
        }

        // 示例2：含负权回路的图
        int n2 = 3;
        SPFAAlgorithm graph2 = new SPFAAlgorithm(n2);
        graph2.addEdge(0, 1, 1);
        graph2.addEdge(1, 2, -1);
        graph2.addEdge(2, 1, -1); // 1->2->1形成负权回路

        int[] dist2 = graph2.spfa(0);
    }
}

代码说明

• 邻接表存储：使用List<List<int[]>>存储图，每个int[]表示一条边（v为邻接节点，w为权重）。
• 距离数组：dist记录起点到各节点的最短路径，初始化为Integer.MAX_VALUE（表示无穷大）。
• 队列与入队标记：queue存储待松弛节点，inQueue避免重复入队，提高效率。
• 负权回路检测：通过cnt数组判断节点入队次数，超过节点总数则判定存在负权回路。

四、SPFA算法的复杂度分析

4.1 时间复杂度

• 平均情况：对于随机图或稀疏图，时间复杂度约为O(m)，m为边数。
• 最坏情况：退化为Bellman-Ford算法的时间复杂度O(n*m)（如在网格图等特殊结构中）。

4.2 空间复杂度

• 主要用于存储邻接表、距离数组、队列等，空间复杂度为O(n + m)，n为节点数，m为边数。

五、SPFA算法的优化与拓展

5.1 优化策略

• 双端队列优化（SLF + LLF）：

  • SLF（Small Label First）：新节点入队时，若其距离小于队首节点的距离，则插入队首，否则插入队尾。
  • LLF（Large Label First）：若队首节点的距离大于队尾节点的距离，则交换二者位置。
    这两种策略可减少节点的松弛次数，在部分场景中提升效率。

• 优先级队列优化：类似Dijkstra算法，用优先级队列（按距离排序）替代普通队列，适用于负权边较少的图，但可能退化为O(m log n)。

5.2 适用场景

• 含负权边的图：如金融交易中的收益/亏损模型（负权表示亏损）。
• 稀疏图：SPFA在稀疏图中效率远高于Bellman-Ford，接近Dijkstra算法。
• 负权回路检测：如电路网络中的负电阻检测、金融套利机会识别（负权回路对应套利路径）。

5.3 局限性

• 稠密图效率低：在稠密图中，SPFA的时间复杂度可能接近O(n*m)，不如Dijkstra算法（优化后O(m log n)）。
• 稳定性差：最坏情况下性能波动较大，不如Bellman-Ford算法稳定（虽慢但时间复杂度固定）。

总结
SPFA算法通过队列筛选待松弛节点，在含负权边的图中高效求解单源最短路径，同时支持负权回路检测，是Bellman-Ford算法的重要优化版本。其核心优势在于“只处理可能更新最短路径的节点”，平均效率远高于Bellman-Ford，尤其适用于稀疏图和含少量负权边的场景。
在实际应用中，需根据图的特点选择算法：

• 无负权边：优先用Dijkstra算法（效率更高）。
• 含负权边但无负权回路：用SPFA算法（平均效率高）。
• 需稳定时间复杂度：用Bellman-Ford算法（适合稠密图）。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～