文稿成果spfa算法

1、SPFA算法SPFA 全稱 Shortest Path Faster Algorithm基本應(yīng)用為快速求解單源最短路 Spfa算法可以說(shuō)是Bellman-ford算法的改進(jìn)版.spfa是利用隊(duì)列來(lái)動(dòng)態(tài)更新最小值. SPFA算法實(shí)現(xiàn)設(shè)Dist代表S到I點(diǎn)的當(dāng)前最短距離，F(xiàn)a代表S到I的當(dāng)前最短路徑中I點(diǎn)之前的一個(gè)點(diǎn)的編號(hào)。開始時(shí)Dist全部為+，只有DistS=0，F(xiàn)a全部為0。 維護(hù)一個(gè)隊(duì)列，里面存放所有需要進(jìn)行迭代的點(diǎn)。初始時(shí)隊(duì)列中只有一個(gè)點(diǎn)S。用一個(gè)布爾數(shù)組記錄每個(gè)點(diǎn)是否處在隊(duì)列中。 SPFA算法實(shí)現(xiàn)每次迭代，取出隊(duì)頭的點(diǎn)v，依次枚舉從v出發(fā)的邊v-u，設(shè)邊的長(zhǎng)度為len，判斷Distv+

2、len是否小于Distu，若小于則改進(jìn)Distu，將Fau記為v，并且由于S到u的最短距離變小了，有可能u可以改進(jìn)其它的點(diǎn)，所以若u不在隊(duì)列中，就將它放入隊(duì)尾。這樣一直迭代下去直到隊(duì)列變空，也就是S到所有節(jié)點(diǎn)的最短距離都確定下來(lái)，結(jié)束算法。若一個(gè)點(diǎn)最短路被改進(jìn)的次數(shù)達(dá)到n ，則有負(fù)權(quán)環(huán)?？梢杂胹pfa算法判斷圖有無(wú)負(fù)權(quán)環(huán)SPFA算法實(shí)現(xiàn)SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過(guò)其它的點(diǎn)之后，過(guò)了一段時(shí)間可能本身被改進(jìn)，于是再次用來(lái)改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。在Be

3、llman-Ford算法中，要是某個(gè)點(diǎn)的最短路徑估計(jì)值更新了，那么我們必須對(duì)所有邊的終點(diǎn)再做一次松弛操作；在SPFA算法中，某個(gè)點(diǎn)的最短路徑估計(jì)值更新，只有以該點(diǎn)為起點(diǎn)的邊指向的終點(diǎn)需要再做一次松弛操作。在極端情況下，后者的效率將是前者的n倍。在平均情況下，SPFA算法的期望時(shí)間復(fù)雜度為O(E)。 要求判斷圖中是否存在負(fù)權(quán)環(huán)(有重邊）Sample Input23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8POJ3259 WormholesSample OutputNOYES2個(gè)test case每個(gè)test case 第一行：N M WN個(gè)點(diǎn)M條雙向

4、正權(quán)邊W條單向負(fù)權(quán)邊 第一個(gè)test case 最后一行3 1 3是單向負(fù)權(quán)邊，3-1的邊權(quán)值是-3/poj3259 Wormholes 判斷有沒(méi)有負(fù)權(quán)環(huán) 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