關于求最短路徑：
求最短路徑的算法有許多種，除了排序外，恐怕是OI界中解決同一類問題算法最多的了。最熟悉的無疑是Dijkstra（不能求又負權邊的圖），接着是Bellman-Ford，它們都可以求出由一個源點向其他各點的最短路徑；如果我們想要求出每一對頂點之間的最短路徑的話，還可以用Floyd-Warshall。
關于松弛：
松弛操作的原理是著名的定理：“三角形兩邊之和大于第三邊”，在資訊學中我們叫它三角不等式。所謂對i,j進行松弛，就是判定是否d[j]>d[i]+w[i,j]，如果該式成立則将d[j]減小到d[i]+w[i,j]，否則不動。
SPFA簡介：
求單源最短路的SPFA算法的全稱是：Shortest Path Faster Algorithm，該算法是西南交通大學段凡丁于1994年發表的（一看到這點就覺得西南交大碉堡了）。它可以在O(kE)的時間複雜度内求出源點到其他所有點的最短路徑，其中k為所有頂點進隊的平均次數，可以證明k一般小于等于2，可以處理負邊，但無法處理帶負環的圖（負環和負邊不是一個概念）。SPFA的實作甚至比Dijkstra或者Bellman_Ford還要簡單。
SPFA算法過程：
我們記源點為S，由源點到達點i的“目前最短路徑”為D[i]，開始時将所有D[i]初始化為無窮大，D[S]則初始化為0。算法所要做的，就是在運作過程中，不斷嘗試減小D[]數組的元素，最終将其中每一個元素減小到實際的最短路徑。
過程中，我們要維護一個隊列，開始時将源點置于隊首，然後反複進行這樣的操作，直到隊列為空：
(1)從隊首取出一個結點u，掃描所有由u結點可以一步到達的結點，具體的掃描過程，随存儲方式的不同而不同；
(2)一旦發現有這樣一個結點，記為v，滿足D[v] > D[u] + w(u, v)，則将D[v]的值減小，減小到和D[u] + w(u, v)相等。其中，w(u, v)為圖中的邊u-v的長度，由于u-v必相鄰，是以這個長度一定已知（不然我們得到的也不叫一個完整的圖）；這種操作叫做松弛。
(3)上一步中，我們認為我們“改進了”結點v的最短路徑，結點v的目前路徑長度D[v]相比于以前減小了一些，于是，與v相連的一些結點的路徑長度可能會相應地減小。注意，是可能，而不是一定。但即使如此，我們仍然要将v加入到隊列中等待處理，以保證這些結點的路徑值在算法結束時被降至最優。
判斷有無負環：
如果某個點進入隊列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）
SPFA算法過程圖解：
如下圖求從源點a到其他點的最短路徑：
1、首先建立起始點a到其餘各點的最短路徑表格，将源點元素（a）入隊列：
2、源點元素（a）出隊，對以a為起始點的所有邊的終點依次進行松弛操作（此處有b,c,d三個點），此時路徑表格狀态為：
注意這裡b，c，d都使d[]數組的值變小了，且不在queue隊列中，所有入隊。
3、隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處隻有e點），此時路徑表格狀态為：
4、隊首元素c點出隊，對以c為起始點的所有邊的終點依次進行松弛操作（此處有e,f兩個點），此時路徑表格狀态為：
注意此時e在隊列中，是以e不用再次入隊列形成 d e f e這種隊列形式，如這樣會增加備援運算。
5、隊首元素d點出隊，對以d為起始點的所有邊的終點依次進行松弛操作（此處隻有g這個點），此時路徑表格狀态為：
6、隊首元素e點出隊，對以e為起始點的所有邊的終點依次進行松弛操作（此處有g這個點），因為d[e]+map[e][g](e到g點的距離)>d[g],故g不進隊列，再說g本來就在隊列裡面了-，-此時隊列的狀态：
7、隊首元素f點出隊，對以f為起始點的所有邊的終點依次進行松弛操作（此處有d，e，g三個點），此時路徑表格狀态為：
d點使路徑表d[d]的值變大了，不如隊列； e，f的最短路徑估值變小了，e在隊列中存在，f不存在。是以e不用入隊了，f要入隊。
8、隊首元素g點出隊，對以g為起始點的所有邊的終點依次進行松弛操作（此處隻有b點），此時路徑表格狀态為：
9、隊首元素e點出隊，對以e為起始點的所有邊的終點依次進行松弛操作（此處隻有g這個點），此時路徑表格狀态為：
d[e]+map[e][g]>d[g],故g不入隊列
10、隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處隻有e這個點），此時路徑表格狀态為：
當隊列為空了，即計算出了從源點帶所有點的最短距離， 由上表知：
a到b的最短路徑是17；
關于算法能否結束？
由上面的示範我們知道，當queue為空的時候，我們就得出結果了。那是否存在queue不為空的時候呢，答案是肯定的。
對于不存在負權回路的圖來說，上述算法是一定會結束的。因為算法在反複優化各個最短路徑長度，總有一個時刻會進入“無法再優化”的局面，此時一旦隊列讀空，算法就結束了。然而，如果圖中存在一條權值為負的回路，就糟糕了，算法會在其上反複運作（因為d[]加上一個負數肯定變下了，是以在有負環的情況下，會不斷有數進入隊列），通過“繞圈”來無休止地試圖減小某些相關點的最短路徑值。假如我們不能保證圖中沒有負權回路，一種“結束條件”是必要的。這種結束條件是什麼呢？
思考Bellman-Ford算法，它是如何結束的？顯然，最樸素的Bellman-Ford算法不管循環過程中發生了什麼，一概要循環|V|-1遍才肯結束。憑直覺我們可以感到，SPFA算法“更聰明一些”，就是說我們可以猜測，假如在SPFA中，一個點進入隊列——或者說一個點被處理——超過了|V|次，那麼就可以斷定圖中存在負權回路了。
【轉載】https://blog.csdn.net/xiao_x_miss/article/details/9721509
關于求最短路徑：
求最短路徑的算法有許多種，除了排序外，恐怕是OI界中解決同一類問題算法最多的了。最熟悉的無疑是Dijkstra（不能求又負權邊的圖），接着是Bellman-Ford，它們都可以求出由一個源點向其他各點的最短路徑；如果我們想要求出每一對頂點之間的最短路徑的話，還可以用Floyd-Warshall。
關于松弛：
松弛操作的原理是著名的定理：“三角形兩邊之和大于第三邊”，在資訊學中我們叫它三角不等式。所謂對i,j進行松弛，就是判定是否d[j]>d[i]+w[i,j]，如果該式成立則将d[j]減小到d[i]+w[i,j]，否則不動。
SPFA簡介：
求單源最短路的SPFA算法的全稱是：Shortest Path Faster Algorithm，該算法是西南交通大學段凡丁于1994年發表的（一看到這點就覺得西南交大碉堡了）。它可以在O(kE)的時間複雜度内求出源點到其他所有點的最短路徑，其中k為所有頂點進隊的平均次數，可以證明k一般小于等于2，可以處理負邊，但無法處理帶負環的圖（負環和負邊不是一個概念）。SPFA的實作甚至比Dijkstra或者Bellman_Ford還要簡單。
SPFA算法過程：
我們記源點為S，由源點到達點i的“目前最短路徑”為D[i]，開始時将所有D[i]初始化為無窮大，D[S]則初始化為0。算法所要做的，就是在運作過程中，不斷嘗試減小D[]數組的元素，最終将其中每一個元素減小到實際的最短路徑。
過程中，我們要維護一個隊列，開始時将源點置于隊首，然後反複進行這樣的操作，直到隊列為空：
(1)從隊首取出一個結點u，掃描所有由u結點可以一步到達的結點，具體的掃描過程，随存儲方式的不同而不同；
(2)一旦發現有這樣一個結點，記為v，滿足D[v] > D[u] + w(u, v)，則将D[v]的值減小，減小到和D[u] + w(u, v)相等。其中，w(u, v)為圖中的邊u-v的長度，由于u-v必相鄰，是以這個長度一定已知（不然我們得到的也不叫一個完整的圖）；這種操作叫做松弛。
(3)上一步中，我們認為我們“改進了”結點v的最短路徑，結點v的目前路徑長度D[v]相比于以前減小了一些，于是，與v相連的一些結點的路徑長度可能會相應地減小。注意，是可能，而不是一定。但即使如此，我們仍然要将v加入到隊列中等待處理，以保證這些結點的路徑值在算法結束時被降至最優。
判斷有無負環：
如果某個點進入隊列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）
SPFA算法過程圖解：
如下圖求從源點a到其他點的最短路徑：
1、首先建立起始點a到其餘各點的最短路徑表格，将源點元素（a）入隊列：
2、源點元素（a）出隊，對以a為起始點的所有邊的終點依次進行松弛操作（此處有b,c,d三個點），此時路徑表格狀态為：
注意這裡b，c，d都使d[]數組的值變小了，且不在queue隊列中，所有入隊。
3、隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處隻有e點），此時路徑表格狀态為：
4、隊首元素c點出隊，對以c為起始點的所有邊的終點依次進行松弛操作（此處有e,f兩個點），此時路徑表格狀态為：
注意此時e在隊列中，是以e不用再次入隊列形成 d e f e這種隊列形式，如這樣會增加備援運算。
5、隊首元素d點出隊，對以d為起始點的所有邊的終點依次進行松弛操作（此處隻有g這個點），此時路徑表格狀态為：
6、隊首元素e點出隊，對以e為起始點的所有邊的終點依次進行松弛操作（此處有g這個點），因為d[e]+map[e][g](e到g點的距離)>d[g],故g不進隊列，再說g本來就在隊列裡面了-，-此時隊列的狀态：
7、隊首元素f點出隊，對以f為起始點的所有邊的終點依次進行松弛操作（此處有d，e，g三個點），此時路徑表格狀态為：
d點使路徑表d[d]的值變大了，不如隊列； e，f的最短路徑估值變小了，e在隊列中存在，f不存在。是以e不用入隊了，f要入隊。
8、隊首元素g點出隊，對以g為起始點的所有邊的終點依次進行松弛操作（此處隻有b點），此時路徑表格狀态為：
9、隊首元素e點出隊，對以e為起始點的所有邊的終點依次進行松弛操作（此處隻有g這個點），此時路徑表格狀态為：
d[e]+map[e][g]>d[g],故g不入隊列
10、隊首元素b點出隊，對以b為起始點的所有邊的終點依次進行松弛操作（此處隻有e這個點），此時路徑表格狀态為：
當隊列為空了，即計算出了從源點帶所有點的最短距離， 由上表知：
a到b的最短路徑是17；
關于算法能否結束？
由上面的示範我們知道，當queue為空的時候，我們就得出結果了。那是否存在queue不為空的時候呢，答案是肯定的。
對于不存在負權回路的圖來說，上述算法是一定會結束的。因為算法在反複優化各個最短路徑長度，總有一個時刻會進入“無法再優化”的局面，此時一旦隊列讀空，算法就結束了。然而，如果圖中存在一條權值為負的回路，就糟糕了，算法會在其上反複運作（因為d[]加上一個負數肯定變下了，是以在有負環的情況下，會不斷有數進入隊列），通過“繞圈”來無休止地試圖減小某些相關點的最短路徑值。假如我們不能保證圖中沒有負權回路，一種“結束條件”是必要的。這種結束條件是什麼呢？
思考Bellman-Ford算法，它是如何結束的？顯然，最樸素的Bellman-Ford算法不管循環過程中發生了什麼，一概要循環|V|-1遍才肯結束。憑直覺我們可以感到，SPFA算法“更聰明一些”，就是說我們可以猜測，假如在SPFA中，一個點進入隊列——或者說一個點被處理——超過了|V|次，那麼就可以斷定圖中存在負權回路了。