透析SPFA算法（图例讲解）

SPFA算法是Bellman-Ford的队列优化，所以先介绍Bellman-Ford算法。

Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。

Bellman-ford算法是求解连通带权图中单源最短路径的一种常用算法，它允许图中存在权值为负的边。同时它还能够判断出图中是否存在一个权值之和为负的回路。如果存在的话，图中就不存在最短路径(因为，假设存在最短路径的话，那么我们只要将这条最短路径沿着权值为负的环路再绕一圈，那么这条最短路径的权值就会减少了，所以不存在最短的路径，因为路径的最小值为负无穷），如果不存在的话，那么求出源点到所有节点的最短路径。

Bellman-Ford算法的限制条件：

要求图中不能包含权值总和为负值回路(负权值回路)，如下图所示。

如果包含了负回路的话，0-1的最短距离可以无限-2+1-2+1...趋近负无穷

三、Bellman-Ford算法思想

考虑：为什么要循环V-1次？

答：因为最短路径肯定是个简单路径，不可能包含回路的，

如果包含回路，且回路的权值和为正的，那么去掉这个回路，可以得到更短的路径

如果回路的权值是负的，那么肯定没有解了

图有n个点，又不能有回路

所以最短路径最多n-1边

又因为每次循环，至少松弛一边

所以最多n-1次就行了

介绍一下松弛计算

松弛计算之前，点B的值是8，但是点A的值加上边上的权重2，得到5，比点B的值（8）小，所以，点B的值减小为5。这个过程的意义是，找到了一条通向B点更短的路线，且该路线是先经过点A，然后通过权重为2的边，到达点B。

当然，如果出现一下情况

则不会修改点B的值，因为3＋4>6。

Bellman－Ford算法可以大致分为三个部分
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：
d（v） > d (u) + w(u,v)
则返回false，表示途中存在从源点可达的权为负的回路。

该算法是利用动态规划的思想。该算法以自底向上的方式计算最短路径。
它首先计算最多一条边时的最短路径(对于所有顶点)。然后,计算最多两条边时的最短路径。外层循环需要执行|V|-1次。

例子

一下面的有向图为例：给定源顶点是0，初始化源顶点距离所有的顶点都是是无穷大的,除了源顶点本身。因为有5个顶点，
因此所有的边需要处理4次。

按照以下的顺序处理所有的边：(B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D).
第一次迭代得到如下的结果(第一行为初始化情况,最后一行为最终结果)：

当 (B,E), (D,B), (B,D) 和 (A,B) 处理完后，得到的是第二行的结果。
当 (A,C) 处理完后，得到的是第三行的结果。
当 (D,C), (B,C) 和 (E,D) 处理完后，得到第四行的结果。

第一次迭代保证给所有最短路径最多只有1条边。当所有的边被第二次处理后，得到如下的结果(最后一行为最终结果)：

第二次迭代保证给所有最短路径最多只有2条边。我们还需要2次迭代(即所谓的松弛操作)，就可以得到最终结果。

还有之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则应为无法收敛而导致不能求出最短路径。
考虑如下的图：

经过第一次遍历后，点B的值变为5，点C的值变为8，这时，注意权重为－10的边，这条边的存在，导致点A的值变为－2。（8＋－10＝－2）

第二次遍历后，点B的值变为3，点C变为6，点A变为－4。正是因为有一条负边在回路中，导致每次遍历后，各个点的值不断变小。

在回过来看一下bellman－ford算法的第三部分，遍历所有边，检查是否存在d（v） > d (u) + w(u,v)。因为第二部分循环的次数是定长的，所以如果存在无法收敛的情况，则肯定能够在第三部分中检查出来。比如

此时，点A的值为－2，点B的值为5，边AB的权重为5，5 > -2 + 5. 检查出来这条边没有收敛。

所以，Bellman－Ford算法可以解决图中有权为负数的边的单源最短路径问。

Dijkstra算法与Bellman算法的区别

Dijkstra算法和Bellman算法思想有很大的区别：
Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。

Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。

如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。

在Bellman算法中判断是否存在从源点可达的负权值回路的方法：

图的存储可以用邻接表或者邻接矩阵，当稠密图的时候邻接矩阵开不了那么大用邻接表，如果用vector做邻接表可可能会超时，所以最好用数组模拟建立邻接表

邻接表的建立:

首先用一个结构体E记录节点的信息，指向那个节点，以及指向节点的权值等信息，给E结构体设置一个next，让它指向H数组，H数组初始化为-1，初始化为-1是为了方便判断某个点直接相连点是否找完了

int H[N];  //存头节点
struct   //记录节点信息
{int v;int count;int next;
}E[N];
int T,n,m,top;
void Readmap(int m)  //读图
{memset(H,-1,sizeof(H));int top=0;for(int i=0;i<m;i++){scanf("%d%d%d",&x[i],&y[i],&c[i]);E[top].v=y[i];E[top].count=c[i];E[top].next=H[x[i]];H[x[i]]=top++;}
}

完整BF算法代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; //点，边，起点
typedef struct Edge //边
{int u, v;int cost;
} Edge;
Edge edge[N];
int dis[N], pre[N];
bool Bellman_Ford()
{for(int i = 1; i <= nodenum; ++i) //初始化dis[i] = (i == original ? 0 : MAX);for(int i = 1; i <= nodenum - 1; ++i)for(int j = 1; j <= edgenum; ++j)if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）{dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;pre[edge[j].v] = edge[j].u;}bool flag = 1; //判断是否含有负权回路for(int i = 1; i <= edgenum; ++i)if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost){flag = 0;break;}return flag;
}void print_path(int root) //打印最短路的路径（反向）
{while(root != pre[root]) //前驱{printf("%d-->", root);root = pre[root];}if(root == pre[root])printf("%d\n", root);
}int main()
{scanf("%d%d%d", &nodenum, &edgenum, &original);pre[original] = original;for(int i = 1; i <= edgenum; ++i){scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);}if(Bellman_Ford())for(int i = 1; i <= nodenum; ++i) //每个点最短路{printf("%d\n", dis[i]);printf("Path:");print_path(i);}elseprintf("have negative circle\n");return 0;
}

由于Bellman-Ford的时间复杂度是O(VE)，E为边的个数，这要比迪杰斯特拉算法慢(Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆) ),所以我们需要优化Bellman-Ford，于是引出来SPFA算法，在平均情况下，SPFA算法的期望时间复杂度为O(kE),k一般小于2，故O(E)

在上面提供的BF算法核心的循环的提前跳出：在实际操作中，贝尔曼-福特算法经常会在未达到V-1次前就出解，V-1其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

具体做法是用一个队列保存待松弛的点，然后对于每个出队的点依次遍历每个与他有边相邻的点（用邻接表效率较高），如果该点可以松弛并且队列中没有该点则将它加入队列中(只有进行松弛操作的点才会对它的邻接点有影响，也就是说其邻接点才需要松弛操作)，如此迭代直到队列为空。

算法流程：

算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。

这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法

SPFA——Shortest Path Faster Algorithm，它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单：

设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞，只有Dist[S]=0，Fa全部为0。

维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。

每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于 Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。

SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。

邻接表版SPFA:

long long SPFA(int st)
{for(int i=1;i<=n;i++)sp[i]=inf;sp[1]=0;queue<int> q;q.push(st);while(!q.empty()){int kai=q.front();q.pop();for(int i=H[kai];i!=-1;i=E[i].next){if(sp[E[i].v]>E[i].count+sp[kai]){sp[E[i].v]=E[i].count+sp[kai];q.push(E[i].v);}}}long long ans=0;for(int i=1;i<=n;i++)ans+=sp[i];return ans;
}

然后是邻接矩阵版本：其中used数组记录是否访问，pre数据记录路径

void spfa(int s,int dis[])
{int i,pre[N];bool used[N];queue<int> q;memset(used,0,sizeof(used));memset(pre,-1,sizeof(pre));for(i=0; i<N; i++)dis[i]=inf;dis[s]=0;used[s]=true;q.push(s);while(!q.empty()){int u=q.front();q.pop();used[u]=false;for(i=0; i<map[u].size(); i++){Node p=map[u][i];if(dis[p.v]>dis[u]+p.len){dis[p.v]=dis[u]+p.len;pre[p.v]=u;if(!used[p.v]){used[p.v]=true;q.push(p.v);}}}}
}

代码实现：

int used[Maxn],outqueue[Maxn],head[Maxn],low[Maxn],n,m;
struct Edge
{int to,w,next;
}edge[Maxm];
bool SPFA (int start)
{queue a;used[start] = 1;low[start] = 0;a.push(start);while (!a.empty()){int top = a.front();a.pop();outqueue[top]++;if (outqueue[top] > n) return false;for (int k = head[top]; k!= -1; k = edge[k].next){if (low[edge[k].to] > low[top] + edge[k].w)low[edge[k].to] = low[top] + edge[k].w;if (!used[edge[k].to]){used[edge[k].to] = 1;a.push(edge[k].to);}}}return true;
}int main()
{while (scanf ("%d%d", &n ,&m) != EOF){memset (used, 0 ,sizeof(used));memset (head, -1 ,sizeof(head));memset (outqueue, 0 ,sizeof(outqueue));memset (low, Max, sizeof(low));int k = 0;while (m--){int a,b,w;scanf ("%d%d%d", &a, &b, &w);edge[k].to = b;edge[k].w = w;edge[k].next = head[a];head[a] = k++;}if (SPFA(1))printf ("%d\n", low[n]);elseprintf ("不存在最短\n");}
}

SPFA在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。

但在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，

通常使用效率更加稳定的Dijkstra算法(无负边的时候用)，有负边用SPFA。

推荐题目:

HDU1874

POJ3159

POJ2502

poj1511

以及其它最短路题目都可以采用SPFA算法