算法介绍：

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

代码实现：

/*************************************************************************    > File Name: SPFA.cpp    > Author: He Xingjie    > Mail: gxmshxj@163.com    > Created Time: 2014年06月12日 星期四 18时24分37秒    > Description:  ************************************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX 50 #define INF 65535typedef struct Edge{    int w;        //边的权值    int end;    //边的终点}Edge;vector
          
            e[MAX]; //动态数组模拟邻接链表存储queue
           
             que; //存储节点int dist[MAX], pre[MAX];bool in[MAX]; //标识是否在队列里面int cnt[MAX]; //记录入队次数int V, E; //顶点数和边数int Init(){ int st, end, weight; cin>>V>>E; for (int i=0; i < E; i++) { cin>>st>>end>>weight; Edge tmp; tmp.w = weight; tmp.end = end; e[st].push_back(tmp); //存入vector } for (int i=0; i< V; i++) { dist[i]= INF; cnt[i] = 0; in[i] = false; pre[i] = 0; }}bool SPFA(int st){ int i, v, end; dist[st] = 0; que.push(st); in[st] = true; cnt[st]++; while (!que.empty()) { v = que.front(); que.pop(); in[v] = false; for (i=0; i
            
              dist[v] + t.w) //更新路径权值,v->end的权值为w { dist[end] = dist[v] + t.w; pre[end] = v; //记录前一个节点 } if (!in[end]) //不在队列里面 { que.push(end); in[end] = true; cnt[end]++; if (cnt[end] > V) //入队次数大于V次 { while (!que.empty()) //清空队列 { que.pop(); } return false; } } } } return true;}void ShowPath(){ int i; stack
             
               st; for (i=0; i
              
               "<
              
             
            
           
          
         
        
       
      
     

输入数据：

5 90 1 32 1 41 4 71 3 10 2 83 0 20 4 -44 3 63 2 -5

输出数据：

 

 

参考：