適用范圍：給定的圖存在負(fù)權(quán)邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過高，SPFA算法便 派上用場了。 我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。當(dāng)然，我們可以在執(zhí)行該算法前做一次拓?fù)渑判?，以判斷是否存在?fù)權(quán)回路，但這不是我們討論的重 點。
算法思想：我們用數(shù)組d記錄每個結(jié)點的最短路徑估計值，用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設(shè)立一個先進(jìn)先出的隊列用來保存待優(yōu)化的 結(jié)點，優(yōu)化時每次取出隊首結(jié)點u，并且用u點當(dāng)前的最短路徑估計值對離開u點所指向的結(jié)點v進(jìn)行松弛操作，如果v點的最短路徑估計值有所調(diào)整，且v點不在 當(dāng)前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結(jié)點來進(jìn)行松弛操作，直至隊列空為止
期望的時間復(fù)雜度O(ke)， 其中k為所有頂點進(jìn)隊的平均次數(shù)，可以證明k一般小于等于2。
實現(xiàn)方法：
建立一個隊列，初始時隊列里只有起始點，再建立一個表格記錄起始點到所有點的最短路徑（該表格的初始值要賦為極大值，該點到他本身的路徑賦為 0）。然后執(zhí)行松弛操作，用隊列里有的點作為起始點去刷新到所有點的最短路，如果刷新成功且被刷新點不在隊列中則把該點加入到隊列最后。重復(fù)執(zhí)行直到隊列 為空。
