最短路径-SPFA算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

/**************************************************************** 
 * Description: SFPA算法
 * Author: Alex Li
 * Date: 2024-08-13 10:30:24
 * LastEditTime: 2024-08-13 10:30:32
****************************************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义一个常量表示无穷大（不可达的距离）
const int INF = INT_MAX;

// 定义边的结构体，包含目标顶点和边的权重
struct Edge {
    int v, weight;
};

// SPFA算法函数，计算从源点source到其他顶点的最短路径
void SPFA(int source, vector<vector<Edge>>& graph, vector<int>& dist) {
    int n = graph.size();  // 获取图的顶点数
    vector<bool> inQueue(n, false);  // 标记每个顶点是否在队列中
    vector<int> count(n, 0);  // 记录每个顶点进入队列的次数，用于检测负权环
    queue<int> q;  // 用于SPFA算法的队列

    // 初始化源点的距离为0，并将源点加入队列
    dist[source] = 0;
    q.push(source);
    inQueue[source] = true;

    // 当队列不为空时，执行以下操作
    while (!q.empty()) {
        int u = q.front();  // 取出队首顶点
        q.pop();  // 从队列中移除该顶点
        inQueue[u] = false;  // 标记该顶点不在队列中

        // 遍历从顶点u出发的所有边
        for (auto& edge : graph[u]) {
            int v = edge.v;  // 获取边的目标顶点
            int weight = edge.weight;  // 获取边的权重

            // 松弛操作：如果从u到v的距离更短，则更新dist[v]
            if (dist[u] != INF && dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;  // 更新目标顶点v的最短距离
                // 如果目标顶点v不在队列中，则将其加入队列
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;  // 标记目标顶点v已加入队列
                    count[v]++;  // 增加目标顶点v进入队列的次数

                    // 如果某个顶点进入队列的次数超过顶点数，则说明存在负权环
                    if (count[v] > n) {
                        cout << "Negative weight cycle detected!" << endl;
                        return;  // 退出算法，检测到负权环
                    }
                }
            }
        }
    }
}

int main() {
    int n, m;  // n是顶点数，m是边数
    cin >> n >> m;

    // 使用邻接表表示图，graph[i]是一个包含从顶点i出发的所有边的列表
    vector<vector<Edge>> graph(n);

    // 输入所有边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});  // 添加从顶点u到顶点v，权重为w的边
    }

    int source;  // 输入源点
    cin >> source;

    // 初始化最短距离数组，所有顶点的初始距离为INF（无穷大）
    vector<int> dist(n, INF);

    // 调用SPFA算法计算最短路径
    SPFA(source, graph, dist);

    // 输出结果，即从源点到各顶点的最短距离
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INF) {
            cout << "INF ";  // 如果顶点不可达，输出INF
        } else {
            cout << dist[i] << " ";  // 输出从源点到顶点i的最短距离
        }
    }
    cout << endl;

    return 0;  // 程序结束
}