spfa講義+前向星優(yōu)化

1、SPFA算法求單源最短路的SPFA算法的全稱是：ShtestPathFasterAlgithm。SPFA算法是西南交通大學(xué)段凡丁于1994年發(fā)表的.從名字我們就可以看出，這種算法在效率上一定有過人之處。很多時(shí)候，給定的圖存在負(fù)權(quán)邊，這時(shí)類似Dijkstra等算法便沒有了用武之地，而BellmanFd算法的復(fù)雜度又過高，SPFA算法便派上用場(chǎng)了。簡(jiǎn)潔起見，我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。當(dāng)然，我們可以在執(zhí)行該算法前

2、做一次拓?fù)渑判?，以判斷是否存在?fù)權(quán)回路，但這不是我們討論的重點(diǎn)。我們用數(shù)組d記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，而且用鄰接表來存儲(chǔ)圖G。我們采取的方法是動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來保存待優(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)來進(jìn)行松弛操作，直至隊(duì)列空為止。定理:只要最

3、短路徑存在，上述SPFA算法必定能求出最小值。出最短路徑長(zhǎng)度后，我們總要說明“怎么走”才算真正解決了問題。如何在計(jì)算過程中記錄下來最短路徑是怎么走的，并在最后將它輸出呢？Path[]數(shù)組，Path[i]表示從S到i的最短路徑中，結(jié)點(diǎn)i之前的結(jié)點(diǎn)的編號(hào)。注意，是“之前”，不是“之后”。最短路徑算法的核心思想成為“松弛”，原理是三角形不等式，方法是上文已經(jīng)提及的。我們只需要在借助結(jié)點(diǎn)u對(duì)結(jié)點(diǎn)v進(jìn)行松弛的同時(shí)，標(biāo)記下Path[v]=u，記錄的

4、工作就完成了。SPFASPFA算法采用圖的存儲(chǔ)結(jié)構(gòu)是鄰接表，方法是動(dòng)態(tài)優(yōu)化逼近法。算算法采用圖的存儲(chǔ)結(jié)構(gòu)是鄰接表，方法是動(dòng)態(tài)優(yōu)化逼近法。算法中設(shè)立了一個(gè)先進(jìn)先出的隊(duì)列法中設(shè)立了一個(gè)先進(jìn)先出的隊(duì)列Queue用來保存待優(yōu)化的頂點(diǎn)，優(yōu)用來保存待優(yōu)化的頂點(diǎn)，優(yōu)化時(shí)從此隊(duì)列里順序取出一個(gè)點(diǎn)化時(shí)從此隊(duì)列里順序取出一個(gè)點(diǎn)w，并且用，并且用w點(diǎn)的當(dāng)前路徑點(diǎn)的當(dāng)前路徑D[W]去優(yōu)化調(diào)整其它各點(diǎn)的路徑值去優(yōu)化調(diào)整其它各點(diǎn)的路徑值D[j]，若有調(diào)整，即，若有

5、調(diào)整，即D[j]的值改小的值改小了，就將了，就將J點(diǎn)放入點(diǎn)放入Queue隊(duì)列以待繼續(xù)進(jìn)一步優(yōu)化。反復(fù)從隊(duì)列以待繼續(xù)進(jìn)一步優(yōu)化。反復(fù)從Queue隊(duì)列里取出點(diǎn)來對(duì)當(dāng)前最短路徑進(jìn)行優(yōu)化，直至隊(duì)空不需要再優(yōu)化隊(duì)列里取出點(diǎn)來對(duì)當(dāng)前最短路徑進(jìn)行優(yōu)化，直至隊(duì)空不需要再優(yōu)化為止，此時(shí)為止，此時(shí)D數(shù)組里就保存了從源點(diǎn)到各點(diǎn)的最短路徑值數(shù)組里就保存了從源點(diǎn)到各點(diǎn)的最短路徑值。下面舉一個(gè)實(shí)例來說明下面舉一個(gè)實(shí)例來說明SFFA算法是怎樣進(jìn)行的：算法是怎樣進(jìn)行的