Massive Algorithms: Shortest Path Faster Algorithm(SPFA)

Shortest Path Faster Algorithm(SPFA) - Graph Algorithm

Shortest Path Faster Algorithm - Wikipedia
The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges. However, the worst-case complexity of SPFA is the same as that of Bellman–Ford, so for graphs with nonnegative edge weights Dijkstra's algorithm is preferred.

http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm
The Shortest Path Faster Algorithm (SPFA) is a single-source shortest paths algorithm whose origin is unknown. It is similar to Dijkstra's algorithm in that it performs relaxations on nodes popped from some sort of queue, but, unlike Dijkstra's, it is usable on graphs containing edges of negative weight, like the Bellman-Ford algorithm. Its value lies in the fact that, in the average case, it is likely to outperform Bellman-Ford (although not Dijkstra's). In theory, this should lead to an improved version of Johnson's algorithm as well.

Algorithm
The basic idea of SPFA is the same as Bellman–Ford algorithm in that each vertex is used as a candidate to relax its adjacent vertices. The improvement over the latter is that instead of trying all vertices blindly, SPFA maintains a queue of candidate vertices and adds a vertex to the queue only if that vertex is relaxed. This process repeats until no more vertex can be relaxed.

Here Q is a first-in, first-out queue of candidate vertices, and w(u, v) is the edge weight of (u, v).

The algorithm can also be applied to an undirected graph by replacing each undirected edge with two directed edge of opposite directions.

The algorithm works by repeatedly selecting a vertex and using it to relax, if possible, all of its neighbors. If a node was successfully relaxed, then it might in turn be necessary to use it to relax other vertices, and hence it is marked for consideration also. Once there are no vertices left to be considered, the algorithm terminates. Note that a vertex might be considered several times during the course of the algorithm. The usual implementation strategy is to use a queue to hold the vertices that might be considered next.

input G,v
for each u ∈ V(G)
     let dist[u] = ∞
let dist[v] = 0
let Q be an initially empty queue
push(Q,v)
while not empty(Q)
     let u = pop(Q)
     for each (u,w) ∈ E(G)
          if dist[w] > dist[u]+wt(u,w)
               dist[w] = dist[u]+wt(u,w)
               if w is not in Q
                    push(Q,w)

Average-case performance
For a random graph, the empirical average time complexity is O(|E|)

Proof of correctness

http://www.nocow.cn/index.php/SPFA

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

这个算法，简单的说就是队列优化的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算法（Shortest Path Faster Algorithm），也是求解单源最短路径问题的一种算法，用来解决：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。 SPFA算法是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算，他的基本算法和Bellman-Ford一样，并且用如下的方法改进： 1、第二步，不是枚举所有节点，而是通过队列来进行优化设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 2、同时除了通过判断队列是否为空来结束循环，还可以通过下面的方法：判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。

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%。在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。

#define MAXV 10000
#define INF 1000000000 //此处建议不要过大或过小,过大易导致运算时溢出,过小可能会被判定为真正的距离
 
using std::vector;
using std::queue;
 
struct Edge{
 int v; //边权
 int to; //连接的点
};
 
vector<Edge> e[MAXV]; //由于一般情况下E<<V*V,故在此选用了vector动态数组存储,也可以使用链表存储
int dist[MAXV]; //存储到原点0的距离,可以开二维数组存储每对节点之间的距离
int cnt[MAXV]; //记录入队次数,超过V则退出
queue<int> buff; //队列,用于存储在SPFA算法中的需要松弛的节点
bool done[MAXV]; //用于判断该节点是否已经在队列中
int V; //节点数
int E; //边数
 
bool spfa(const int st){ //返回值:TRUE为找到最短路返回,FALSE表示出现负环退出
 for(int i=0;i<V;i++){ //初始化:将除了原点st的距离外的所有点到st的距离均赋上一个极大值
  if(i==st){
   dist[st]=0; //原点距离为0;
   continue;
  }
  dist[i]=INF; //非原点距离无穷大
 }
 buff.push(st); //原点入队
 done[st]=1; //标记原点已经入队
 cnt[st]=1; //修改入队次数为1
 while(!buff.empty()){ //队列非空,需要继续松弛
  int tmp=buff.front(); //取出队首元素
  for(int i=0;i<(int)e[tmp].size();i++){ //枚举该边连接的每一条边
   Edge *t=&e[tmp][i]; //由于vector的寻址速度较慢,故在此进行一次优化
   if(dist[tmp]+(*t).v<dist[(*t).to]){ //更改后距离更短,进行松弛操作
    dist[(*t).to]=dist[tmp]+(*t).v; //更改边权值
    if(!done[(*t).to]){ //没有入队,则将其入队
     buff.push((*t).to); //将节点压入队列
     done[(*t).to]=1; //标记节点已经入队
     cnt[(*t).to]+=1; //节点入队次数自增
     if(cnt[(*t).to]>V){ //已经超过V次,出现负环
      while(!buff.empty())buff.pop(); //清空队列,释放内存
      return false; //返回FALSE
     }
    }
   }
  }
  buff.pop();//弹出队首节点
  done[tmp]=0;//将队首节点标记为未入队
 }
 return true; //返回TRUE
} //算法结束
 
int main(){ //主函数
 scanf("%d%d",&V,&E); //读入点数和边数
 for(int i=0,x,y,l;i<E;i++){
  scanf("%d%d%d",&x,&y,&l); //读入x,y,l表示从x->y有一条有向边长度为l
  Edge tmp; //设置一个临时变量,以便存入vector
  tmp.v=l; //设置边权
  tmp.to=y; //设置连接节点
  e[x].push_back(tmp); //将这条边压入x的表中
 }
 if(!spfa(0)){ //出现负环
  printf("出现负环,最短路不存在\n");
 }else{ //存在最短路
  printf("节点0到节点%d的最短距离为%d",V-1,dist[V-1]);
 }
 return 0;
}

Also check http://www.wutianqi.com/?p=2285

http://www.java3z.com/cwbwebhome/article/article1/1361.html?id=4734
　　我们用数组dist记录每个结点的最短路径估计值，而且用邻接表(或邻接矩阵）来存储图G。采取的方法是动态逼近法：

设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作（看程序注释），如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

　　定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。
　　证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dist[v]变小。所以算法的执行会使dist越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着dist值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）

　判断有无负环：如果某个点进入队列的次数超过N（图的顶点数）次则存在负环（SPFA无法处理带负环的图）

在一幅图中，我们仅仅知道结点一个节点到另一个节点的最短路径长度是多少，有时候意义不大。这附图如果是地图的模型的话，在算出最短路径长度后，我们总要说明“怎么走”才算真正解决了问题。如何在计算过程中记录下来最短路径是怎么走的，并在最后将它输出呢？

Path[] 数组，Path[i]表示从S到i的最短路径中，结点i之前的结点的编号。注意，是“之前”，不是“之后”。
我们只需要在借助结点u对结点v进行松弛的同时，标记下Path[v] = u，记录的工作就完成了，可递归输出。

Read full article from Shortest Path Faster Algorithm - Wikipedia

Shortest Path Faster Algorithm(SPFA) - Graph Algorithm

Proof of correctness

Labels

Popular Posts