SPFA算法是在bellman-ford算法基础上优化而来，所以我们先讨论bellman-ford算法
bellman-ford算法的核心是‘松弛’。那么什么是松弛呢？以下图为例：
假设数组d[i]表示源点s到达结点i的最短路径长度，那么松弛指的就是当d[a] + w < d[b]，也就是说，这时候通过a到达b比原来的路径更短，此时，我们松弛d[b] = d[a] + w;
bellman-ford算法核心思想简单，就是对m条边进行n-1次松弛操作，得到最短路径，如果还能松弛，说明存在负权环。如下所示
如果一直绕着负环，那么负环上的结点的最短距离都是-INF。
bellman-ford算法的伪代码如下
我的代码：
1 void bellman(){ 2 fill(d,d + maxn,INF); 3 d[1] = 0; 4 5 for(int i = 1; i <= n-1; i++){ 6 memcpy(backup,d,sizeof d); 7 for(int j = 1; j <= m; j++){ 8 int v = edg[j].v; 9 int u = edg[j].u; 10 int w = edg[j].w; 11 d[v] = min(d[v],backup[u] + w); 12 } 13 } 14 }
backup数组是因为外层循环还有另一层含义，就是经过最多i条边，能完成的最短路径生成。
注意到，一个结点被更新是由于它的起始结点被更新，那么，我们使用bfs优化，将被更新的结点储存下来，这里要注意，需要使用inq[]数组储存结点是否在队列中。
以下是SPFA代码(非常像Dijkstr)：
1 bool SPFA(){ 2 memset(d,0x3f,sizeof d); 3 queue<int> q; 4 //1 q中元素都是被更新过的结点，为了防止重复更新结点，需要设置 5 //cnt[i] 表示到达结点i最短路径经过的边数 6 for(int i = 1; i <= n; i++){ 7 inq[i] = true; 8 q.push(i); 9 } 10 //这个for循环是有些题目是判断是否有负环，而不是是否有从1开始的负环，那么我们就将所有结点入队。 11 while(!q.empty()){ 12 int u = q.front(); 13 q.pop(); 14 inq[u] = false; 15 16 int len = G[u].size(); 17 for(int i = 0; i < len; i++){ 18 int v = G[u][i].first; 19 int w = G[u][i].second; 20 if(d[u] + w < d[v]){ 21 d[v] = d[u] + w; 22 if(!inq[v]){ 23 q.push(v); 24 cnt[v] = cnt[u] + 1; 25 inq[v] = true; 26 if(cnt[v] >= n) return false; 27 } 28 } 29 } 30 } 31 32 33 return true; 34 }
值得注意的是，cnt数组起到了和bellman-ford算法外循环类似的作用。一般来说，有负权边的问题都需要bellman-ford或者SPFA算法，但是正权边也可以先使用SPFA算法（虽然可能被卡，但是速度快）。