SPFA

yyycj · 2025-07-29 18:02:01 · 算法·理论

SPFA 与 Dijkstra 一样，都是求最短路的算法，但 SPFA 可以求边权为负数的最短路。

SPFA 是基于 Bellman-Ford 算法的优化版本，Bellman-Ford 算法的核心是松弛操作，也就是更新最短路。

我们观察每一个没有负环的图，就会发现，每个点的最短路需要走的边数都不超过 n-1，所以此算法最多需要 n-1 次松弛。

每次松弛，我们遍历每一条边，如果从这条边的起点的最短路加边权小于终点的最短路，那我们就应该更新终点的最短路，和 Dijsktra 的松弛操作大致相同。

代码：

int u[M], v[M], w[M], dis[N];

void spfa(int n, int m, int s) {
    memset(dis, INT_INF, sizeof dis);
    dis[s] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
                dis[v[j]] = min(dis[v[j]], dis[u[j]] + w[j]);
        }
    }
}

但这样做的时间复杂度到达了 O(nm)，所以就有了 SPFA。我们发现如果这个点需要修改最短路，那么一定是它的某个起点被修改了，所以 SPFA，做的就是每进行完一次松弛后，将改变了最短路的点能够到达的点放进一个队列里，这样下次松弛时，就只需要对队列里的点进行改变。

这样做的时间复杂度会根据图的形状来改变，但在随机图的情况下效率较高。

代码：

struct node {
    int p, w;
};

int dis[N];
bool vis[N];
vector<node> edge[N];

void spfa(int s) {
    queue<int> q;
    memset(dis, INT_INF, sizeof dis);
    q.push(s);
    dis[s] = 0;
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = false;
        for (node i : edge[u]) {
            if (dis[i.p] > dis[u] + i.w) {
                dis[i.p] = dis[u] + i.w;
                if (!vis[i.p]) {
                    q.push(i.p);
                    vis[i.p] = true;
                }
            }
        }
    }
}