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)<dist(i)，则将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原创，转载请注明出处：