文稿成果spfa算法_第1頁
文稿成果spfa算法_第2頁
文稿成果spfa算法_第3頁
文稿成果spfa算法_第4頁
免費預(yù)覽已結(jié)束,剩余7頁可下載查看

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

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

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

3、llman-Ford算法中,要是某個點的最短路徑估計值更新了,那么我們必須對所有邊的終點再做一次松弛操作;在SPFA算法中,某個點的最短路徑估計值更新,只有以該點為起點的邊指向的終點需要再做一次松弛操作。在極端情況下,后者的效率將是前者的n倍。在平均情況下,SPFA算法的期望時間復(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個test case每個test case 第一行:N M WN個點M條雙向

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論