《短路算法之spfa》ppt課件

《《短路算法之spfa》ppt課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、SPFA/ShortestPathFasterAlgorithmBellman-FordBellman-ford算法是求含負(fù)權(quán)圖的單源最短路徑算法，效率很低，但代碼很容易寫。即進(jìn)行不停地松弛（原文是這么寫的，為什么要叫松弛，爭(zhēng)議很大），每次松弛把每條邊都更新一下，若n-1次松弛后還能更新，則說(shuō)明圖中有負(fù)環(huán)，無(wú)法得出結(jié)果，否則就成功完成。RelaxationRELAX(u,v)ifdis[v]>dis[u]+w(u,v)thendis[v]=dis[u]+w(u,v);//π[v]=u;Bellman-FordBELLMAN-FORDfori=1to

2、V

3、-1d

4、oforeveryedge(u,v)inEdoRELAX(u,v);//O(VE)隊(duì)列優(yōu)化我們用數(shù)組dis記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，而且用鄰接表來(lái)存儲(chǔ)圖G。我們采取的方法是動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來(lái)進(jìn)行松弛操作，直至隊(duì)列空為止。隊(duì)列基本操作ENQUEUE(Q,v)tail++;Q[tail]=v;DEQUEUE(Q)head++;DEQ

5、UEUE=Q[head];EMPTY(Q)returnhead>=tail;SPFASPFAINITIALIZE;ENQUEUE(Q,s);whilenotEMPTY(Q)u=DEQUEUE(Q);foreveryvertexvinadj[u]doifdis[v]>dis[u]+w(u,v)dis[v]=dis[u]+w(u,v);//π[v]=uifnotvinQENQUEUE(Q,s);//O(kE)循環(huán)隊(duì)列ENQUEUE(Q,v)tail=(tail+1)modlen;Q[tail]=v;DEQUEUE(Q)head=(head+1)modlen;DEQU

6、EUE=Q[head];EMPTY(Q)returnhead=tail;