深入了解spfa算法是如何優化bellman-ford的

原文：https://blog.csdn.net/u011893609/article/details/81232124 

前言

Bellman-Ford算法，限于資料匮乏和時間複雜度比Dijkstra算法高，包括白書在内的很多資料，都沒說得太明白。對于優化後的SPFA算法也沒有提及。

而且最短路問題通常是作為圖論的入門問題，學習者通常沒有圖論基礎，不知道圖論的一些基本常識，看已有的資料很容易産生疑惑。其實，從Bellman-ford算法優化到SPFA算法實際上是順理成章的。

Bellman-Ford算法有什麼用。

Bellman-Ford算法是用來解決單源最短路問題的。

在現實生活旅遊途中，我們通常想知道一個景點到其他所有景點的最短距離，以友善我們決定去哪些比較近的景點。而這時候，Bellman-Ford算法就有用了。

Bellman-Ford算法的優點是可以發現負圈，缺點是時間複雜度比Dijkstra算法高。

而SPFA算法是使用隊列優化的Bellman-Ford版本，其在時間複雜度和程式設計難度上都比其他算法有優勢。

算法流程

（1）初始化：将除起點s外所有頂點的距離數組置無窮大 d[v] = INF, d[s] = 0

（2）疊代：周遊圖中的每條邊，對邊的兩個頂點分别進行一次松弛操作，直到沒有點能被再次松弛

（3）判斷負圈：如果疊代超過V-1次，則存在負圈

總結

定理一：隻有上一次疊代中松弛過的點才有可能參與下一次疊代的松弛操作

疊代的實際意義：每次疊代k中，我們找到了經曆了k條邊的最短路。

“沒有點能夠被松弛”時，疊代結束

根據定理一“隻有上一次疊代中松弛過的點才有可能參與下一次疊代的松弛操作”，似乎算法中周遊每條邊的做法比較菜，我們隻需要考慮那些被成功松弛的點的鄰點不就好了嗎？答案是肯定的。我們可以簡單地通過一個隊列來維護這些被成功松弛的點，這個小小的改進可以帶來巨大加速，改進之後的算法被稱為SPFA。

直覺了解負圈

符合常識地，有定理二：如果在邊權都為正的圖中，最短路一定是一條路徑，而不是一個圈，且長度不會大于等于V

拓展到存在負邊權的圖中，有定理三：對于存在負圈的圖，最短路無意義

定理四：對于不存在負圈的圖，最短路一定是一條路徑，且長度不會大于等于V