图论算法：SPFA 算法

什么是 SPFA 算法？

SPFA（Shortest Path Faster Algorithm）是一种用于计算单源最短路径的算法。与 Dijkstra 算法不同，SPFA 可以处理带有 负权边 的图。它实际上是 Bellman-Ford 算法的一种队列优化版本。

核心思想

SPFA 算法的核心思想是 动态逼近。它维护一个队列，队列中存放着“刚刚被成功松弛过”的顶点。只有当一个顶点的距离 dist[u] 变小时，它才有可能去更新它的邻居 v 的距离 dist[v]。因此，只有那些距离值变小的顶点，才需要被放入队列中，作为下一轮松弛操作的出发点。

这个优化使得 SPFA 在稀疏图中通常比 Bellman-Ford 算法表现得更高效。

算法流程

1. 初始化:

   • 创建一个距离数组 dist，dist[source] = 0，其他所有 dist 值为无穷大。
   • 创建一个队列 q，并将源点 source 入队。
   • 创建一个布尔数组 in_queue，标记顶点是否在队列中。in_queue[source] = true。

2. 循环: 当队列 q 不为空时： a. 从队头取出一个顶点 u，并标记 in_queue[u] = false。 b. 遍历 u 的所有出边 (u, v)，进行 松弛操作： 如果 dist[u] + weight(u, v) < dist[v]，则： i. 更新 dist[v] = dist[u] + weight(u, v)。 ii. 如果 v 当前不在队列中，则将 v 入队，并标记 in_queue[v] = true。

负环检测

SPFA 算法的一个重要应用是检测图中是否存在 负环（一个边权之和为负数的环）。如果在负环上，最短路可以无限小。

检测方法很简单：记录每个顶点入队的次数。如果某个顶点入队次数超过了 N（图中顶点的总数），那么可以断定图中存在负环。这是因为在一个不包含负环的图中，每个顶点最多只会被松弛 N-1 次。

C++ 伪代码

#include <vector>
#include <queue>
#include <limits>

const int INF = std::numeric_limits<int>::max();

bool spfa(int s, int n, const std::vector<std::vector<std::pair<int, int>>>& adj, std::vector<int>& dist) {
    dist.assign(n + 1, INF);
    std::vector<int> count(n + 1, 0);
    std::vector<bool> in_queue(n + 1, false);
    std::queue<int> q;

    dist[s] = 0;
    q.push(s);
    in_queue[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                    count[v]++;
                    if (count[v] > n) {
                        return false; // 发现负环
                    }
                }
            }
        }
    }
    return true; // 没有负环
}

关于 SPFA

• 时间复杂度: 在最好情况下，SPFA 的时间复杂度是 O(E)，其中 E 是边的数量。但在最坏情况下（例如在特意构造的网格图中），它的时间复杂度会退化到 O(V*E)，与 Bellman-Ford 相同。
• 关于“SPFA 已死”: 在算法竞赛中，由于 SPFA 的最坏情况性能不佳，且容易被针对性数据卡住，因此在没有负权边的图中，强烈建议使用更稳定的 Dijkstra 算法。只有在处理带负权边且没有负环的最短路问题时，SPFA 才是主要选择。