摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

大家忍忍吧  大致上都是簡體的  (  要看動漫  就是要練習看簡體  (誤  )

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

算法简介

SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。也有人说SPFA本来就是Bellman-Ford算法，现在广为流传的Bellman-Ford算法实际上是山寨版。

算法流程

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

这个算法，简单的说就是队列优化的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左右

算法代码

Procedure SPFA; 

Begin   
    initialize-single-source(G,s);   
    initialize-queue(Q);   
    enqueue(Q,s);   
    while not empty(Q) do begin      
        u:=dequeue(Q);      
        for each v∈adj[u] do begin    
           tmp:=d[v];         
           relax(u,v);         
        if (tmp<>d[v]) and (not v in Q) then enqueue(Q,v);         
        end;      
      end;
End;

procedure spfa;
begin
fillchar(q,sizeof(q),0); h:=0; t:=0;//队列
fillchar(v,sizeof(v),false);//v[i]判断i是否在队列中
for i:=1 to n do dist[i]:=maxint;//初始化最小值 

inc(t); q[t]:=1; v[1]:=true;dist[1]:=0;//这里把1作为源点 
while not(h=t) do
begin    
    h:=(h mod n)+1;x:=q[h];  v[x]:=false;    
    for i:=1 to n do     
       if (cost[x,i]>0)and(dist[x]+cost[x,i]<dist[i]) then     
       begin       
         dist[i]:=dist[x]+cost[x,i];       
         if not(v[i]) then       
         begin         
           t:=(t mod n)+1; q[t]:=i;v[i]:=true;       
        end;     
      end;
end;
end;

void SPFA(void)//好久以前写的……今天丢上来……话说我都不记得SPFA怎么写了……囧……ms存图是矩阵……嗯嗯
{ 
   int i; 
   queue list; 
   list.insert(s); 
　　for(i=1;i<=n;i++)  　
　　　　{   
　　　　　if(s==i)    
　　　　　　continue;   
　　　　　dist[i]=map[s][i];   
　　　　　way[i]=s;   
　　　　　if(dist[i])   
　　　　　list.insert(i);  
　　　　} 
　　int p; 
　　while(!list.empty()) 
　　　{  
　　　　　p=list.fire();  
　　　　　for(i=1;i<=n;i++)   
　　　　　　　if(map[p][i]&&(dist[i]>dist[p]+map[p][i]||!dist[i])&&i!=s)    
　　　　　　　　　{     
　　　　　　　　　　dist[i]=dist[p]+map[p][i];     
　　　　　　　　　　way[i]=p;     
　　　　　　　　　　if(!list.in(i))      
　　　　　　　　　　list.insert(i);    
　　　　　　　　　} 
　　　}
}

以下為另一篇搜到的資料

來源 : http://baike.baidu.com/view/682464.html?fromTaglist

/**********************************************************/

　　求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。 
　　SPFA算法是西南交通大学段凡丁于1994年发表的.
　　从名字我们就可以看出，这种算法在效率上一定有过人之处。 
　　很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，
   而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 
　　简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。
   当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。 
　　我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。
   我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，
   优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，
   如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。
   这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 
　　定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。 
　　证明：每次将点放入队尾，都是经过松弛操作达到的。
   换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。
   由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。
   因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，
   算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕） 
　　期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
　　实现方法：建立一个队列，初始时队列里只有起始点，
　　在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。
　　然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，
　　如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空
　　判断有无负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）