Bellman - Ford, SPFA 学习笔记（含有负权的单源最短路径）

Bellman-Ford算法

　　Bellman-Ford可以用来解决含有负权图的单源最短路径（Dijkstra不能解决这种问题）。代码简单，但是效率低。具体的过程就是不停的松弛，每次松弛进行一次更新。如果更新n次仍然还可以更新，说明图中存在负环，直接跳出就可以。这种情况下无解。

　　Bellman-Ford的时间复杂度是O(ve).

伪代码如下：

1 Bellman-Ford(G,w,s) ：{ //图G ，边集 函数 w ，s为源点
2 for each vertex v ∈ V（G） do //初始化 1阶段
3 d[v] ←+∞
4 d[s] ←0; //1阶段结束
5 for i=1 to |v|-1 do //2阶段开始，双重循环。
6 for each edge（u,v） ∈E(G) do //边集数组要用到，穷举每条边。
7 If d[v]> d[u]+ w(u,v) then //松弛判断
8 d[v]=d[u]+w(u,v) //松弛操作 2阶段结束
9 for each edge（u,v） ∈E(G) do
10 If d[v]> d[u]+ w(u,v) then
11 Exit false
12 Exit true
13 }

　　

　　SPFA算法

　　因为Bellman-Ford的算法冗余的部分太多，有很多不必要的计算。所以可以用队列对其进行优化，这就是我们所说的SPFA算法。由西南交大的在1994年提出。SPFA同样是解决含有负权图的单元最短路径。其实就是对Bellman-Ford的优化。据说还有一些八卦的消息，说SPFA其实就是Bellman-Ford算法，而现在流传的Bellman-Ford是山寨版，这里就不深究了，哈。

　　SPFA算法的思路就是：设立一个队列，优化队列中的元素u的dis[u]，并对每一个与u相连的节点v进行松弛。如果dis[v] > dis[u] + w(u, v)，dis[v] = dis[u] + w(u, v)，并且如果当前的v不在队列里边(inqueue[v] == false)，则v入队列并标记inqueue[v] = true。不断松弛，直到队列为空。

　　这样看来SPFA很想BFS，其实写法上SPFA类似BFS，不过有一点不同的是。对队列中的节点u取出并且松弛完一次与u相邻的所有节点v以后，将u再次标记为不在队列，即inqueue[u] = false；这样才能实现对u（也就是每一个节点）进行多次松弛，直到队列为空。

　　当然，如果图中含有负环，松弛会一直进行下去（总能找到div[v] > div[u] + w(u, v)）。从Bellman-Ford中知道，一个节点最多被松弛n次，如果超过，则说明有负环，无解。这里可以加一个cnt[]记录每一个节点出现过的次数。保证cnt[i]<=n，否则跳出。

　　SPFA算法期望的时间复杂度是O(ke)，其中k是每个节点尽对的平均次数。k一般是小于2的。

　　实现代码如下：

　

1 bool spfa() {
2 int i, u, v, z;
3 for(i = 0; i < gv; ++i) {
4 dis[i] = inf; cnt[i] = 0; inq[i] = false;
5 }
6 q.push(s); inq[s] = true;
7 dis[s] = 0; cnt[s]++;
8
9 while(!q.empty()) {
10 u = q.front();
11 for(i = head[u]; i; i = g[i].next) {
12 v = g[i].to; z = g[i].val;
13 if(dis[v] > dis[u] + z) {
14 dis[v] = dis[u] + z;
15 if(!inq[v]) {
16 cnt[v]++;
17 inq[v] = true;
18 if(cnt[v] > n) return false; //存在负环
19 q.push(v);
20 }
21 }
22 }
23 inq[u] = false; //重新标记为false，实现多次松弛
24 q.pop();
25 }
26 return true;
27 }

　　SPFA算法有两个优化算法 SLF 和 LLL：
　　SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)　　LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。

　　SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。

总体比较：

　　在Bellman-Ford算法中，要是某个点的最短路径估计值更新了，那么我们必须对所有边指向的终点再做一次松弛操作；

　　在SPFA算法中，某个点的最短路径估计值更新，只有以该点为起点的边指向的终点需要再做一次松弛操作。

　　spfa算法能够避免很多冗余的松弛，使O(ve)的复杂度降到O(ke).

AC_Von原创，转载请注明出处：http://www.cnblogs.com/vongang/archive/2012/03/05/2380127.html