C++ SPFA算法解析

C++ SPFA算法解析

SPFA（Shortest Path Faster Algorithm）算法是一种用于求解带负权边的单源最短路径问题的算法。它基于Bellman-Ford算法，通过使用队列优化，使得在大多数情况下比Bellman-Ford算法更高效。本文将详细介绍SPFA算法的原理、应用场景以及如何在C++中实现该算法。

SPFA算法简介

SPFA算法适用于权值有负值且没有负圈的图的单源最短路径问题。论文中的复杂度为O(kE)，其中k为每个节点进入Queue的次数，且k一般<=2。但这个复杂度证明是有问题的，实际上SPFA的最坏情况应该是O(VE)。

引例

输入格式

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

三个整数n，m，s，分别表示点的个数、有向边的个数、出发点的编号。

接下来m行，包含三个整数u，v，w，表示u-->v，长度为w。

输出格式

输出一行n个整数，第i个表示s到第i个点的最短路径，若不能到达则输出2^31 - 1。

输入样例

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例

0 2 4 3

代码实现

初始化

我们需要一个数组来记录一个点到某个点的最短距离，我们可以定义一个cost数组来记录权值。最大值可定义为2e6 + 9（即2000009），不能到达则输出2^31 - 1（即2147483647）。

const int N = 2e6 + 9; // const常量，不可改变,数尽量大一些
const int INF = 2147483647;
int n, m, s, u, v, w;

void AddEdge() {} // 连边函数

signed main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        AddEdge(u, v, w); // 待会进行的连边所使用的函数
    }
}

连边

我们需要定义一个结构体Edge然后进行连边操作。

int cnt = 0, head[N];

struct Edge {
    int nxt, to, val;
} edge[N];

void AddEdge(int from, int to, int val) {
    cnt++; // 记录操作次数
    edge[cnt].nxt = head[from];
    edge[cnt].to = to;
    edge[cnt].val = val;
    head[from] = cnt;
}

SPFA函数的编写

在SPFA函数中，我们需要进行vis数组的清零，需要用memset函数来执行，让cost[n]里的各数值为INF，即作为无穷大的数，当不可到达时，可直接输出cost[i]（i为各个点），可到达时，使用min（）函数可求最短路径，将cost[s]（即起点）的数值为0，因为它的到它自己本身的距离为0。

int vis[N], cost[N];

void SPFA() {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i)
        cost[i] = INF;
    cost[s] = 0;
}

定义一个队列q，每次取队头执行松弛操作，添加起点。

void SPFA() {
    ……
    cost[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = 1; // 让起点 s 标记为 1，代表已进入队列
}

当队列不为空时，进行循环。

void SPFA() {
    ……
    vis[s] = 1;
    while (!q.empty()) {
        int x = q.front(); // 获取队头数字
        q.pop(); // 弹出队头
        vis[x] = 0; // 队头已取出，此时取出的队头数字的 vis[队头数字] 改为 0 代表出队
    }
}

以下代码段为松弛操作（以便不懂的小伙伴）

if (cost[y] > cost[x] + edge[i].val) {
    cost[y] = cost[x] + edge[i].val;
    if (vis[y] == 0) {
        vis[y] = 1;
        q.push(y);
    }
}

队头已取出，此时取出的队头数字的vis[队头数字]改为0代表出队。

void SPFA() {
    ……
    while (!q.empty()) {
        ……
        vis[x] = 0;
        for (int i = head[x]; i; i = edge[i].nxt) {
            int y = edge[i].to; // 代表为 i 时的 edge的下一个指向
            if (cost[y] > cost[x] + edge[i].val) { // 如果 指向（未更改原本存储）的权值 大于 x 的权值 + 指向的权值
                cost[y] = cost[x] + edge[i].val; // 进行 权值 的 更改
                if (vis[y] == 0) { // 判断是否曾进入队列
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}

最后在主程序中进行权值的输出。

signed main() {
    ……
    SPFA();
    for (int i = 1; i <= n; ++i) {
        cout << cost[i];
    }
}

最终代码

using namespace std;
const int N = 2e6 + 9; // const常量，不可改变
const int INF = 2147483647;
int n, m, s, u, v, w;
int cnt = 0, head[N], vis[N], cost[N];

// 定义边结构体
struct Edge {
    int nxt, to, val;
} edge[N];
// 添加边
// 添加一条边，from为起点，to为终点，val为边的权值
void AddEdge(int from, int to, int val) {
    // 计数器加1
    cnt++;
    // 将新边的下一条边设为当前起点边的下一条边
    edge[cnt].nxt = head[from];
    // 将新边的终点设为to
    edge[cnt].to = to;
    // 将新边的权值设为val
    edge[cnt].val = val;
    // 将当前起点边的下一条边设为新边
    head[from] = cnt;
}
// SPFA算法，用于求解单源最短路径问题
void SPFA() {
    // 初始化访问数组，将所有节点标记为未访问
    memset(vis, 0, sizeof(0));
    // 初始化所有节点的最短路径长度为无穷大
    for (int i = 1; i <= n; ++i)
        cost[i] = INF;
    // 源节点的最短路径长度为0
    cost[s] = 0;
    // 创建一个队列，用于存储待处理的节点
    queue<int> q;
    // 将源节点加入队列
    q.push(s);
    // 标记源节点为已访问
    vis[s] = 1;
    // 当队列不为空时，继续处理
    while (!q.empty()) {
        // 取出队首节点
        int x = q.front();
        // 将队首节点从队列中移除
        q.pop();
        // 标记队首节点为未访问
        vis[x] = 0;
        // 遍历队首节点的所有邻接节点
        for (int i = head[x]; i; i = edge[i].nxt) {
            // 获取邻接节点的编号
            int y = edge[i].to;
            // 如果通过队首节点到达邻接节点的路径更短，则更新邻接节点的最短路径长度
            if (cost[y] > cost[x] + edge[i].val) {
                cost[y] = cost[x] + edge[i].val;
                // 如果邻接节点未被访问，则将其加入队列
                if (vis[y] == 0) {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}
signed main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        AddEdge(u, v, w);
    }
    SPFA();
    for (int i = 1; i <= n; ++i) {
        cout << cost[i] << " ";
    }
}

SPFA的负环判断

洛谷负环判断模板题目：传送门

我将上述代码的变量cnt循环次数改为tim，创建了一个cnt数组，用来储存每个数的入队次数。

存储的是入队次数而不是松弛次数

int cnt[N];

题目部分要求

若u >= 0，则表示存在一条从u至υ边权为w的边，还存在一条从υ至u边权为w的边。
若u < 0，则只表示存在一条从u至υ边权为w的边。

主程序main中的部分代码段应改为

for (int i = 1; i <= m; ++i) {
    cin >> u >> v >> w;
    AddEdge(u, v, w);
    if (w >= 0)
        AddEdge(v, u, w);
}

最终程序

using namespace std;
const int N = 3e6 + 9;
const int INF = 3e6 + 10;
int T;
int n, m, u, v, w, tim, head[N], vis[N], cost[N], cnt[N]; // cnt 换成 tim, 且创建 cnt 数组
struct Edge {
    int nxt, to, val;
} edge[N];
// 清空函数: start
void Clear() {
    memset(edge, 0, sizeof(edge));
    tim = 0;
    memset(head, 0, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(cost, INF, sizeof(cost));
    memset(cnt, 0, sizeof(cnt));
}
// 清空函数: end
void AddEdge(int from, int to, int val) {
    tim++; // 原本的cnt需改成tim，含义一致
    edge[tim].nxt = head[from];
    edge[tim].to = to;
    edge[tim].val = val;
    head[from] = tim;
}
bool SPFA() {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i) cost[i] = INF;
    cost[1] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for (int i = head[x]; i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (cost[v] > cost[x] + edge[i].val) {
                cost[v] = cost[x] + edge[i].val;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                    cnt[v]++; // 记录 edge[i].to 的次数
                    if (cnt[v] >= n) return true; // 如果 入队次数 已经 大于等于 n
                }
            }
        }
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) { // 重复循环次数
        Clear(); // 进行清空
        cin >> n >> m;
        for (int i = 1; i <= m; ++i) {
            cin >> u >> v >> w;
            AddEdge(u, v, w);
            if (w >= 0) AddEdge(v, u, w); // 更改的地方
        }
        cout << (SPFA() ? "YES" : "NO") << endl; // 更改的地方
    }
}

因为进行多次数组的询问，我们要清空之前的数据

以上就是有关SPFA的知识点，感谢你能看到这里！Cheer！

相关练习

• 洛谷 P3371：传送门

相关资料

• 最短路相关算法复杂度比较
• SPFA需要队列的原因
• SPFA算法解析
• 链式前向星 相关知识_1
• 链式前向星 相关知识_2