一、Bellman-Ford算法
最優(yōu)性原理
它是最優(yōu)性原理的直接應用，算法基于以下事實：
l 如果最短路存在，則每個頂點最多經(jīng)過一次，因此不超過n-1條邊；
l 長度為k的路由長度為k-1的路加一條邊得到；
l 由最優(yōu)性原理，只需依次考慮長度為1，2，…，k-1的最短路。
適用條件&范圍
l 單源最短路徑(從源點s到其它所有頂點v);
l 有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖);
l 邊權(quán)可正可負(如有負權(quán)回路輸出錯誤提示);
l 差分約束系統(tǒng)（需要首先構(gòu)造約束圖，構(gòu)造不等式時>=表示求最小值, 作為最長路，<=表示求最大值, 作為最短路。<=構(gòu)圖時, 有負環(huán)說明無解；求不出最短路（為Inf）為任意解。>=構(gòu)圖時類似）。
算法描述
l 對每條邊進行|V|-1次Relax操作;
l 如果存在(u,v)∈E使得dis[u]+w<dis[v],則存在負權(quán)回路;否則dis[v]即為s到v的最短距離,pre[v]為前驅(qū)。
時空復雜度
for i:=1 to |V|-1 do
for 每條邊(u,v)∈E do Relax(u,v,w);
for每條邊(u,v)∈E do
if dis[u]+w<dis[v] Then Exit(False)
算法時間復雜度O(VE)。因為算法簡單，適用范圍又廣，雖然復雜度稍高，仍不失為一個很實用的算法。
改進和優(yōu)化 如果循環(huán)n-1次以前已經(jīng)發(fā)現(xiàn)不存在緊邊則可以立即終止； Yen氏改進（不降低漸進復雜度）；SPFA算法
二、 SPFA算法
算法簡介
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一種隊列實現(xiàn)，減少了不必要的冗余計算。 它可以在O(kE)的時間復雜度內(nèi)求出源點到其他所有點的最短路徑，可以處理負邊。
算法流程
SPFA對Bellman-Ford算法優(yōu)化的關(guān)鍵之處在于意識到：只有那些在前一遍松弛中改變了距離估計值的點，才可能引起他們的鄰接點的距離估計值的改變。因此，算法大致流程是用一個隊列來進行維護，即用一個先進先出的隊列來存放被成功松弛的頂點。初始時，源點s入隊。當隊列不為空時，取出隊首頂點，對它的鄰接點進行松弛。如果某個鄰接點松弛成功，且該鄰接點不在隊列中，則將其入隊。經(jīng)過有限次的松弛操作后，隊列將為空，算法結(jié)束。SPFA算法的實現(xiàn)，需要用到一個先進先出的隊列 queue 和一個指示頂點是否在隊列中的標記數(shù)組mark。為了方便查找某個頂點的鄰接點，圖采用臨界表存儲。
算法代碼
Procedure SPFA;
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do begin
u:=dequeue(Q);
for each v∈adj[u] do begin
tmp:=d[v]; relax(u,v);
if (tmp<>d[v]) and (not v in Q) then enqueue(v);
end;
end;
End;
負環(huán)處理
需要特別注意的是：僅當圖不存在負權(quán)回路時，SPFA能正常工作。如果圖存在負權(quán)回路，由于負權(quán)回路上的頂點無法收斂，總有頂點在入隊和出隊往返，隊列無法為空，這種情況下SPFA無法正常結(jié)束。
判斷負權(quán)回路的方案很多，世間流傳最廣、比較容易實現(xiàn)并且高效的方法的是記錄每個結(jié)點進隊次數(shù)，超過|V|次表示有負權(quán)。
三、 學以致用
POJ 1201 Intervals 差分約束系統(tǒng)
設(shè)S(i)為 0..i-1 中在最終序列中的的整數(shù)個數(shù)。則約束條件如下:
S(b)-S(a) >= c
0 <= S(i+1) - S(i) <= 1 <==> S(i+1)-S(i) >= 0;
S(i)-S(i+1) >= -1
注意本題要求的是最小值, 而按照>=號建圖后發(fā)現(xiàn)圖中有負環(huán), 怎么辦呢?
其實很簡單, 本題求的不是最短路, 而是最長路! Bellman_ford即可!
POJ 1275 Cashier Employment 出納員的雇傭
黑書上有詳細講解
POJ 1364 King 差分約束系統(tǒng)
這個題目構(gòu)圖之后, 只需要用bellman_ford判斷是否有負圈.
構(gòu)圖方法:
首先進行轉(zhuǎn)換:a[j]+...+a[j+m] = a[1]+...a[j+m] - (a[1]+...+a[j-1]) = sum[j+m] -
sum[j-1] >(<) ki. 差分約束只能全部是<=或者(>=).
第二步轉(zhuǎn)換: sum[j+m]-sum[j-1] <= ki-1 或者 sum[j-1]-sum[j+m] <= -ki-1.
約束圖構(gòu)造好后就是簡單的Bellman-Ford了!
POJ 1716 Integer Intervals 是1201的簡單版本, 貪心算法能夠得到更好的效果.
POJ 2983 Is the Information Reliable?
差分約束題, 處理一下等號的情況, 然后普通的Bellman_ford
POJ 3159 Candies 最短路徑
Bellman-Ford超時, Dijkstra算法可以高效解決, SPFA(隊列)居然超時...SPFA修改為堆棧實現(xiàn)就過了.
POJ 3169 Layout 差分約束
Bellman-Ford 和 SPFA 實現(xiàn)均可
POJ 3259 Wormholes 判斷負權(quán)回路
TOJ 2976 Path 單純的最短路徑 可練習SPFA
ZOJ 3033 Board Games 我做的第一道Bellman-Ford題目
首先，DFS判斷可達性，不可達直接輸出infinity結(jié)束，可達，bellman-ford判斷是否存在負環(huán)，存在輸出infinity，否則，輸出最短距離。
四、 參考資料
《算法導論》；《算法藝術(shù)與信息學競賽》；《算法藝術(shù)與信息學競賽學習指導》；NOCOW；百度百科；alpc55的小地方；highkobe；（謝謝分享）
p.s.：匆匆總結(jié)拿來分享，如有不當之處，望指出！----By Fandywang