SPFA

SPFA（Shortest Path Faster Algorithm）是一种用于计算加权图中单源最短路径的算法，是 Bellman-Ford 算法的改进版本。SPFA 算法在大多数情况下比 Bellman-Ford 算法更快，尤其是在稀疏图中。它使用了队列来优化松弛操作，使得每个节点在更新时只被处理一次，从而提高了效率。

算法原理

SPFA 的基本思想是通过维护一个队列，来存储当前可能需要松弛的节点。每当一个节点的最短路径被更新时，它就被加入队列。这样，SPFA 可以确保每个节点在最短路径被确定之前只被处理一次。

算法步骤

1. 初始化:

   • 设置源点到自身的距离为 0。
   • 设置源点到其他所有节点的距离为正无穷（表示不可达）。
   • 使用一个队列来存储待处理的节点。

2. 松弛操作:

   • 从队列中取出一个节点，遍历其所有邻接节点。
   • 对每条边 (u, v) 进行松弛操作，如果通过 u 到达 v 的距离小于当前 v 的距离，则更新 v 的距离。
   • 如果更新了 v 的距离，且 v 不在队列中，则将 v 加入队列。

3. 重复处理:

   • 重复上述过程，直到队列为空。

代码实现

以下是 SPFA 算法的 C++ 实现：

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

using namespace std;

struct Edge {
    int to, weight;
};

void spfa(int source, int V, vector<vector<Edge>>& graph) {
    vector<int> dist(V, numeric_limits<int>::max()); // 初始化距离为无穷大
    vector<bool> inQueue(V, false); // 标记节点是否在队列中
    dist[source] = 0; // 源点到自身的距离为0

    queue<int> q;
    q.push(source);
    inQueue[source] = true;

    while (!q.empty()) {
        int u = q.front(); // 取出队首元素
        q.pop();
        inQueue[u] = false;

        // 遍历 u 的所有邻接边
        for (const auto& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // 松弛操作
            if (dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;

                // 如果 v 不在队列中，则加入队列
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }

    // 打印结果
    for (int i = 0; i < V; ++i) {
        if (dist[i] == numeric_limits<int>::max()) {
            cout << "Distance from source to vertex " << i << " is infinity" << endl;
        } else {
            cout << "Distance from source to vertex " << i << " is " << dist[i] << endl;
        }
    }
}

int main() {
    int V, E;
    cout << "Enter number of vertices and edges: ";
    cin >> V >> E;

    vector<vector<Edge>> graph(V); // 使用邻接表表示图
    cout << "Enter edges (u, v, weight):" << endl;
    for (int i = 0; i < E; ++i) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u].push_back({v, weight}); // 添加边
    }

    int source;
    cout << "Enter source vertex: ";
    cin >> source;

    spfa(source, V, graph);

    return 0;
}

代码解析

1. 数据结构:

   • 使用 struct Edge 表示边，包含目标节点 to 和边的权重 weight。
   • 使用 vector<vector<Edge>> graph 来存储图的邻接表。

2. 初始化:

   • 初始化距离数组 dist，源点的距离为 0，其他节点的距离为无穷大。
   • 使用 vector<bool> inQueue 来标记节点是否在队列中。

3. 主循环:

   • 从队列中取出一个节点 u，并遍历所有与 u 相连的边。
   • 对每条边进行松弛操作，如果更新了目标节点的距离且该节点不在队列中，则将其加入队列。

4. 输出结果:

   • 打印每个节点到源点的最短距离。

时间复杂度

• SPFA 算法的时间复杂度为 (O(E)) 在稀疏图中，平均情况下性能良好，但在最坏情况下（例如图中存在负权环时）可能退化为 (O(VE))。

优势与劣势

优势:

• SPFA 算法在许多实际应用中表现良好，尤其是在稀疏图中。
• 能够处理负权边，并且比 Bellman-Ford 更快。

劣势:

• 在某些特定情况下（例如图中存在大量边的负权环），可能会退化为较慢的性能。

SPFA 算法是一种有效的单源最短路径算法，适用于加权图，尤其是稀疏图。通过使用队列来优化松弛操作，使得算法在大多数情况下比传统的 Bellman-Ford 算法更快。它的实现简单且易于理解，适合处理实际问题中的最短路径计算。