思想
SPFA 算法是对 Bellman-Ford 算法的优化。
我们令一张图中所有顶点的数量为 \(n\)，所有边的数量为 \(m\)。
在 Bellman-Ford 算法中，我们需要对每一条边进行松弛操作，所以最终复杂度为 \(O(nm)\)。
显然按照这种方法，可以处理含有负边权的图。
我们考虑到，在 Bellman-Ford 算法中，是否每一次松弛都使他们路径变短了，显然不是的。这就会导致浪费了许多的时间。
那么我们的 SPFA 算法正是对这一点进行了优化处理。
在 Bellman-Ford 算法中显而易见的问题是，有些松弛操作可能不会使路径变短。
那我们考虑，什么情况下一些点进行松弛操作路径会变短。
我们定义一个数组，\(dist_i\) 表示编号为 \(i\) 的点到原点的最短距离。
显然，若 \(i\) 顶点被松弛过后，\(dist_i\) 变短了，则 \(i\) 顶点的出边所连接的顶点也会由于松弛操作而变短。
那么我们只用考虑一个顶点 \(i\)，若这个顶点被松弛后路径变短了，去松弛与它出边相接的顶点。
做法：
我们定义一个队列 \(q\)，用来存储将要松弛的顶点。
除了刚才定义的 \(dist\) 数组，我们另外定义一个数组 \(vis\)，这里的 \(vis\) 数组与 dijkstra 所表示的含义不同，这里的 \(vis_i\) 表示的是编号为 \(i\) 的顶点当前是否在队列 \(q\) 中。
我们从起始点 \(s\) 开始，将 \(s\) 放入队列，\(vis_s=1\)。将与起始点的出边相接的所有点进行松弛，将 \(dist\) 变短的所有顶点放入队列（初始化无穷大，起始点松弛时显然全部点都变短了），我们每次对当前顶点的所有出边连接的点进行松弛时，记得将当前点弹出队列，并取消 \(vis\) 标记，因为当前点肯定已经松弛完毕了。
接下来，我们每次取出队列的第一个顶点，对当前点的所有出边连接的点进行松弛，若松弛后路径变短，并且 \(vis\) 还未打上标记，则将这个点放入队列，打上 \(vis\) 标记（其实 \(vis\) 数组就是防止重复进入队列）。
我们重复进行该操作，直到所有顶点的 \(dist\) 都是最优路径，即当队列 \(q\) 为空时。
特性
显然，我们可以用 SPFA 处理含负边权的图。并且我们可以判断一个图是否存在负权回路（即一个所有边的边权和为负数的环）。
判断负权回路/负环做法：
根据 SPFA 的思想，每个点最多被其他 \(n-1\) 个点各松弛一次，如果存在负环，那么一部分点就会在这个负环中无限松弛，无限缩短路径。
所以我们可以记录每个点被松弛的次数，若被某个点被松弛的次数大于等于 \(n\)，那么说明这个图存在负环。否则不存在负环。
代码
令一张图中所有顶点的数量为 \(n\)，所有边的数量为 \(m\)。
最坏时间复杂度 \(O(nm)\)。
最坏情况即所有的边都需要进行松弛。
SPFA 的最坏时间复杂度达到了 Bellman-Ford 的平均复杂度。
优化还是很不错的，但是赛时确实容易被卡。
代码实现：
int dist[N];
queue<int>q;
bool vis[N];
void SPFA(){
memset(dist,0x3f,sizeof(dist));
dist[s] = 0;
q.push(s);
vis[s] = 1;
while (!q.empty()){
int tmp = q.front();
q.pop();
vis[tmp] = 0;
for (int i = head[tmp];i != 0;i = e[i].nxt){
int v = e[i].to;
int w = e[i].w;
if (dist[v] > dist[tmp] + w){
dist[v] = dist[tmp] + w;
if (!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
}