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

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

2、做一次拓撲排序，以判斷是否存在負權(quán)回路，但這不是我們討論的重點。我們用數(shù)組d記錄每個結(jié)點的最短路徑估計值，而且用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設立一個先進先出的隊列用來保存待優(yōu)化的結(jié)點，優(yōu)化時每次取出隊首結(jié)點u，并且用u點當前的最短路徑估計值對離開u點所指向的結(jié)點v進行松弛操作，如果v點的最短路徑估計值有所調(diào)整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結(jié)點來進行松弛操作，直至隊列空為止。定理:只要最

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

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

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