文稿成果spfa算法

1、SPFA算法SPFA 全称 Shortest Path Faster Algorithm基本应用为快速求解单源最短路 Spfa算法可以说是Bellman-ford算法的改进版.spfa是利用队列来动态更新最小值. SPFA算法实现设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+，只有DistS=0，Fa全部为0。 维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。 SPFA算法实现每次迭代，取出队头的点v，依次枚举从v出发的边v-u，设边的长度为len，判断Distv+

2、len是否小于Distu，若小于则改进Distu，将Fau记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有节点的最短距离都确定下来，结束算法。若一个点最短路被改进的次数达到n ，则有负权环。可以用spfa算法判断图有无负权环SPFA算法实现SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。在Be

3、llman-Ford算法中，要是某个点的最短路径估计值更新了，那么我们必须对所有边的终点再做一次松弛操作；在SPFA算法中，某个点的最短路径估计值更新，只有以该点为起点的边指向的终点需要再做一次松弛操作。在极端情况下，后者的效率将是前者的n倍。在平均情况下，SPFA算法的期望时间复杂度为O(E)。 要求判断图中是否存在负权环(有重边）Sample Input23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8POJ3259 WormholesSample OutputNOYES2个test case每个test case 第一行：N M WN个点M条双向

4、正权边W条单向负权边 第一个test case 最后一行3 1 3是单向负权边，3-1的边权值是-3/poj3259 Wormholes 判断有没有负权环 spfa by guo wei#include #include #include #include using namespace std;int F,N,M,W;const int INF = 1 30;struct Edge int e,w;Edge(int ee,int ww):e(ee),w(ww) Edge() ;vector G1000;int updateTimes1000;int dist1000;int Spfa(int

5、 v)for( int i = 1; i = N; +i)disti = INF;distv = 0;queue que;que.push(v);memset(updateTimes ,0,sizeof(updateTimes);while( !que.empty() int s = que.front();que.pop();for( int i = 0;i dists + Gsi.w ) diste = dists + Gsi.w;que.push(e); +updateTimese; if( updateTimese = N) return true;return false;int main()cin F;while( F-) cin N M W;for( int i = 1; i 1000; +i)Gi.clear();for( int i = 0; i s e t;Gs.push_back(Edge(e,t);Ge.push_back(Edge(s,t);for( int i = 0;i s e t