SPFA 最短路
进阶SPFA 是 Bellman-Ford 的队列优化版本，平均 O(E)，最坏 O(VE)。
// 算法讲解
SPFA 最短路
演示 SPFA（队列优化的 Bellman-Ford）求最短路的过程。
待机
速度 中
待机 ⌨1bool spfa(int src, int V, vector<vector<pair<int,int>>>& adj, vector<long long>& dist) {
2 dist.assign(V, LLONG_MAX);
3 vector<int> cnt(V, 0);
4 vector<bool> inQueue(V, false);
5 queue<int> q;
6 dist[src] = 0;
7 q.push(src);
8 inQueue[src] = true;
9 while (!q.empty()) {
10 int u = q.front(); q.pop();
11 inQueue[u] = false;
12 for (auto [v, w] : adj[u]) {
13 if (dist[u] + w < dist[v]) {
14 dist[v] = dist[u] + w;
15 if (!inQueue[v]) {
16 q.push(v);
17 inQueue[v] = true;
18 if (++cnt[v] > V) return false;
19 }
20 }
21 }
22 }
23 return true;
24}
复杂度分析
时间 平均 O(E), 最坏 O(VE)
空间 O(V)
最优 O(E)
最坏 O(VE)
算法讲解
SPFA 用队列维护待松弛的节点，每次取出队首节点松弛其邻居。
如果邻居距离被更新且不在队列中，则加入队列。
可以检测负权环：如果某个节点入队次数超过 V 次，则存在负环。
平均复杂度 O(E)，但最坏情况仍为 O(VE)。