C++实现SPFA算法模板代码

资源摘要信息:"SPFA模板，即最短路径快速算法（Shortest Path Faster Algorithm）模板，是用于解决图论中单源最短路径问题的一种算法。该算法由Edward Fredkin提出，是Bellman-Ford算法的一个优化版本，通过使用队列优化来减少不必要的计算，从而在许多情况下提高效率。 SPFA算法的核心思想是使用一个队列来保存待松弛的边。算法开始时，将源点加入队列，并对所有边进行初始化。在算法的每次迭代中，都会从队列中取出一个顶点，并对该顶点的每一个邻接点进行松弛操作。如果通过该顶点可以达到更短的路径，则更新该邻接点的距离，并将其加入队列，以便后续的松弛操作。整个过程会持续进行，直到队列为空。 SPFA算法的时间复杂度在理论上是O(VE)，其中V是顶点的数量，E是边的数量。然而，在实际操作中，由于使用了队列进行优化，因此在稀疏图上的表现通常会比Bellman-Ford算法好很多。但是需要注意的是，SPFA算法在稠密图上可能退化到接近O(V^2)的时间复杂度，所以在稠密图上使用时需要谨慎。 以下是一个简单的SPFA算法的C++实现模板： ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; const int MAXN = 100010; // 假设最大顶点数为100010 const int INF = 0x3f3f3f3f; // 用一个足够大的数表示无穷 int n, m; // n为顶点数，m为边数 int head[MAXN], dist[MAXN], vis[MAXN]; // head为邻接表的头指针数组，dist为距离数组，vis为标记数组 struct Edge { int to, next, w; // to为目标顶点，next为下一条边，w为边的权重 } edge[2 * MAXN]; // 假设边数最多为顶点数的两倍 void SPFA(int s) { queue<int> q; // 使用队列 fill(dist, dist + n, INF); // 初始化所有距离为无穷大 dist[s] = 0; // 源点到自己的距离为0 q.push(s); // 将源点加入队列 vis[s] = 1; // 标记源点已经进入队列 while (!q.empty()) { int u = q.front(); // 取出队首元素 q.pop(); vis[u] = 0; // 标记该点已经离开队列 for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (!vis[v]) { // 只有当v未在队列中时才将其加入队列 q.push(v); vis[v] = 1; } } } } } int main() { // 读取顶点数和边数 cin >> n >> m; fill(head, head + n, -1); // 初始化邻接表头指针数组 // 读取边信息并构建邻接表 for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; // 读取边的起点、终点和权重 edge[i * 2].to = v; edge[i * 2].w = w; edge[i * 2].next = head[u]; head[u] = i * 2; edge[i * 2 + 1].to = u; edge[i * 2 + 1].w = w; edge[i * 2 + 1].next = head[v]; head[v] = i * 2 + 1; } // 使用SPFA算法求解单源最短路径 SPFA(0); // 假设0是源点 // 输出结果 for (int i = 0; i < n; i++) { if (dist[i] == INF) cout << "INF" << endl; else cout << dist[i] << endl; } return 0; } ``` 在上述代码中，首先定义了邻接表的结构体`Edge`，用来存储图的边信息。然后实现了SPFA算法的主要逻辑，包括初始化队列、松弛操作以及队列的维护。最后在`main`函数中读取图的边信息，并调用`SPFA`函数进行单源最短路径的计算，最后输出每个顶点到源点的最短路径长度。需要注意的是，上述代码中的队列优化是通过`vis`数组来标记某个顶点是否已经在队列中，如果不在队列中则可以将其加入队列进行松弛操作。 对于SPFA算法的优化和变种，比如检测负权环的方法，可以通过记录每个点入队的次数来实现。如果一个点的入队次数超过了点数减一（即n-1），则说明存在从该点出发的负权环。这是因为如果图中不存在负权环，则最短路径的长度最多只会经过n-1条边（从源点出发，经过n-1个不同的点到达第n个点）。如果某个顶点入队次数超过这个限制，则必然是由于负权环导致的。 SPFA算法在求解正权图的单源最短路径问题时非常高效，但是由于其理论时间复杂度较高，在最坏情况下可能退化到O(V^2)，所以在稠密图上可能不如Floyd-Warshall算法或者Dijkstra算法配合优先队列高效。不过，在稀疏图上SPFA算法仍然是一个很好的选择。"