本文主要介绍 C++ 中 SPFA 和 BFS 两种算法。其中，SPFA 是一种非常高效的最短路算法，而 BFS 则是一种广度优先搜索算法。对于这两种算法，我们将分别从算法原理、C++ 实现方式和算法优缺点等方面进行详细介绍。

关键词：C++、SPFA、BFS、最短路、广度优先搜索

一、SPFA 算法

1.1 算法原理

SPFA 算法（Shortest Path Faster Algorithm）是一种非常高效的最短路算法。其基本思想是利用队列进行松弛操作，即将源点到当前点的距离和当前点到其他点的距离进行比较，如果存在更短的路径，则更新最短路径并入队。直到队列为空为止。

该算法的时间复杂度为 O(kE)，其中 k 为一个小于等于 2 的常数，E 为边数。当图中存在负权边时，该算法可能会陷入死循环，因此需要进行优化。

1.2 C++ 实现方式

下面是 SPFA 算法的 C++ 实现方式：

cppCopy Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

int n, m;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; 
}

bool spfa() {
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    st[1] = true;
    q.push(1);

    while (q.size()) {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return false;
    return true;
}

int main() {
    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if (!spfa()) puts("impossible");
    else cout << dist[n] << endl;

    return 0;
}

1.3 算法优缺点

SPFA 算法的主要优点是时间复杂度比 Dijkstra 算法还要低，尤其是在稀疏图中表现更加优秀。其缺点则是存在负权边时可能会陷入死循环，因此需要进行优化。

二、BFS 算法

2.1 算法原理

BFS 算法（Breadth-First Search）是一种广度优先搜索算法。其基本思想是从起点开始，逐层遍历所有能够到达的顶点，直到找到目标顶点为止。

该算法的时间复杂度为 O(E+V)，其中 E 为边数，V 为顶点数。

2.2 C++ 实现方式

下面是 BFS 算法的 C++ 实现方式：

cppCopy Code
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e3 + 10;

int g[N][N];
int dist[N];
bool st[N];

int n, m;

void bfs() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);

    while (q.size()) {
        auto t = q.front();
        q.pop();

        for (int i = 1; i <= n; i++) {
            if (g[t][i]) {
                int j = i;
                if (dist[j] > dist[t] + g[t][j]) {
                    dist[j] = dist[t] + g[t][j];
                    if (!st[j]) {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) cout << "-1" << endl;
    else cout << dist[n] << endl;
}

int main() {
    cin >> n >> m;

    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;
    }

    bfs();

    return 0;
}

2.3 算法优缺点

BFS 算法的主要优点是时间复杂度比 DFS 算法要低，而且在最短路径求解中表现非常出色。其缺点则是空间复杂度较高，因为需要维护一个队列。

三、结论

本文介绍了 C++ 中的 SPFA 和 BFS 算法。其中，SPFA 是一种非常高效的最短路算法，而 BFS 则是一种广度优先搜索算法。别看两个差不多，实际上区别很大

---

饭后提示：本文并不是讲述区别，就是想用BFS衬托一下SPFA，不过SPFA这货也不是啥好玩意，人家很多最短路都用了DF了（Dijkstra Floyd）

---

拉后提示：

都是图论中常用的算法，但它们的作用和实现方式有很大的区别。

BFS是一种用于图的遍历的算法，它从图中的某个顶点开始，首先访问这个顶点，然后依次访问与这个顶点相邻的未被访问过的顶点，然后再以这些相邻顶点为起点，继续访问它们的相邻顶点，依次类推。BFS通常用于寻找图中的最短路径、拓扑排序等问题。

SPFA则是用于计算图中单源最短路径的算法，其原理基于Bellman-Ford算法，但在实际应用中对Bellman-Ford算法进行了优化。SPFA通过不断地松弛边来更新节点的距离值，直到无法更新为止。与Dijkstra算法相比，SPFA能够处理带有负权边的图，并且在一般情况下具有更好的性能。

因此，BFS主要用于图的遍历和搜索，而SPFA则主要用于解决图中的单源最短路径问题。