spfa算法求最短路问题

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)；

我个人感觉spfa算法和堆优化的dijkstra算法算是有点相似的，只不过是dijkstra用的是优先队列，spfa用的是普通队列，spfa还有一个区别于dijkstra的是，spfa每个点可能遍历不止一次，而dijkstra每个点只需要遍历一次，并且spfa还适用于图中存在负权边的情况，spfa相比于dijkstra和bellman-ford还是毕竟全能的。

代码模板：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<set>
 8 #include
 9 #include
10 #include
11 #include<string>
12 #define ll long long
13 #define ull unsigned long long
14 #define inf 0x3f3f3f3f
15 #define inff 0x7fffffff
16 using namespace std;
17 const int N = 100000 + 10;
18 const int M = 1000000 + 10;
19 const ll mod = 1e9 + 7;
20 
21 bool vis[N];
22 int cut[N];
23 int dis[N];
24 
25 struct Edge {
26     int v, cost;
27 };
28 
29 vectorE[N];
30 
31 void addedge(int u, int v, int w) {
32     E[u].push_back({ v,w });
33 }
34 
35 bool spfa(int start, int n) {
36 
37     memset(vis, false, sizeof(vis));
38     for (int i = 0; i <= n; i++) dis[i] = inf;
39     vis[start] = true;
40     dis[start] = 0;
41     queue<int>que;
42     while (!que.empty()) que.pop();
43     que.push(start);
44     vis[start] = false;
45     memset(cut, 0, sizeof(cut));
46     cut[start] = 1;
47     while (!que.empty()) {
48         int u = que.front();
49         que.pop();
50         vis[u] = false;
51         for (int i = 0; i < E[u].size(); i++) {
52             int v = E[u][i].v;
53             if (dis[v] > dis[u] + E[u][i].cost) {
54                 dis[v] = dis[u] + E[u][i].cost;
55                 if (!vis[v]) {
56                     vis[v] = true;
57                     que.push(v);
58                     cut[v]++;
59                     if (cut[v] > n) return false;
60                 }
61             }
62         }
63     }
64 
65     return true;
66 }
67 
68 int main() {
69 
70     int n, m;
71     cin >> n >> m;
72     for (int i = 1; i <= m; i++) {
73         int u, v, w;
74         cin >> u >> v >> w;
75         addedge(u, v, w);
76     }
77     if (spfa(1, n)) {
78         if (dis[n] != inf) cout << dis[n] << "\n";
79         else cout << "impossible" << "\n";
80     }
81     else cout << "impossible" << "\n";
82 
83     return 0;
84 }
 
最短路问题

相关

最短路问题——弗洛伊德算法(Floyd)

最短路问题

标签