Bellman-Ford算法（下文中簡稱為BF）與Dijkstra算法一樣，解決的是單源最短路徑問題。兩者不同之處在于晃酒，后者只適用于無負權(quán)邊的圖贝次，而BF無此限制：無論是否有向蛔翅，無論是否有負權(quán)邊，只要圖中沒有負權(quán)環(huán)山析，則該算法可以正確地給出起點到其余各點的最短路徑笋轨，否則報告負權(quán)環(huán)的存在爵政。

很多資料（比如維基百科）在解釋BF時都會提到它的基礎(chǔ)或者核心是松弛操作钾挟。自然地等龙，理解BF的關(guān)鍵也是理解這一點，所以下面就來專門講講它究竟是個什么意思黍衙。

“松弛”荠诬，翻譯自英文的relaxation柑贞，原本指數(shù)學(xué)上的一種迭代求解方程組的方法，表示通過改進近似解來不斷地逼近最終解或者說最優(yōu)解的方法棠众。而我們下面可以看到闸拿，BF正是這么一個迭代改進的過程空盼。

岔開一筆揽趾，我不知道當(dāng)初數(shù)學(xué)家們?yōu)槭裁匆x用relaxation這個詞篱瞎，但我覺得它的字面意義正好與它所代表的實際過程相反（在BF中尤其如此）俐筋。更糟的是吼野，數(shù)學(xué)中另有一個“松弛”的概念瞳步，使用的是同一個詞单起。它表示的是一種解決問題的技巧：如果問題難以解決嘀倒，則放寬某些限制测蘑，將其轉(zhuǎn)化成容易解決的問題，以求得近似的解決方案（這倒是名副其實）勇蝙。所以，在理解BF時挨约，看到“松弛”這個詞味混，如果覺得它有誤導(dǎo)之嫌，不妨在腦中將其替換為“逼近”或者“改進”诫惭。

那么BF中的松弛改進是個怎么樣的操作呢翁锡？

首先，松弛改進的對象很明顯夕土，就是從起點到其余各點的距離馆衔。給定圖G和起點s，G[u][v]表示邊(u, v)的長度，且用D[u]表示從s點到某個u點已知的（但不一定是最優(yōu)的）最短路徑的長度哈踱，那么對于圖中任何從該u點出發(fā)的邊(u, v)荒适，如果D[u] + G[u][v]小于D[v]，則將D[v]松弛改進為D[u] + G[u][v]开镣。我們可以用Python給出下面的實現(xiàn)（代碼出自Python Algorithms一書陕壹，稍有改動怎憋，下同）：

inf = float('inf')

def relax(G, u, v, D, P):
    o = D.get(v, inf) # 若D[v]不存在則返回inf
    n = D.get(u, inf) + G[u][v]
    if n < o:
        D[v], P[v] = n, u
        return True # 若有改進，則返回True
    return False

其次，根據(jù)定義，它肯定是一個迭代的過程教馆。照上面的分析和代碼谍婉，我們可以將每次松弛改進和某條邊對應(yīng)起來唤蔗。講到這里，那么BF的核心思想其實就很容易描述了：不斷地選擇一條邊，做松弛改進操作掘殴，直到得出正確的解答病瞳。

接下來的問題自然就是：

1. 這種思路能提供一個正確的算法嗎笼踩？換言之挟冠，我們?nèi)绾瓮ㄟ^選擇松弛改進邊的順序肋僧，使得對應(yīng)的BF最終完成運行辫诅？
2. 如何選擇松弛改進邊的順序，使得對應(yīng)的BF效率最高？

我們先來考察如下的情況：如果對圖里每條邊按照隨機的順序都做一次松弛改進（稱之為一輪松弛改進），能得到什么操灿？能夠保證起點s的任一鄰點（記作u）都得到正確的D[u]（最短路徑長度）和P[u]（最短路徑中的上一節(jié)點）嗎救鲤？顯然不能。比如下圖中，如果依次松弛改進(s, a)、(s, b)阶女、(s, c)憔杨、(a, b)妖啥、(b, c)，那么一輪下來骑脱，確實a點b點c點都能得到正確答案稚瘾。但如果順序變成(b, c)、(a, b)骏全、(s, a)、(s, b)、(s, c)苹熏，那么b點的答案就是錯的（讀者可自行推演驗證）干发。

image

怎么去找這么個最優(yōu)的順序呢蔬崩？這樣的話，只需一輪松弛改進就可以解決問題了术唬。其實這是不現(xiàn)實的。因為要得到這個最優(yōu)順序捌治，從本質(zhì)上來講趋艘，必須得將各點以距起點s的最短距離從小到大作一個排序疲恢，而這正就是要解決的問題。這是個“循環(huán)依賴”瓷胧，沒有出路显拳。

回到上圖完成一輪松弛改進之時〈晗簦可以發(fā)現(xiàn)杂数，雖然b點的答案不一定正確，但是a點和c點的答案瘸洛，不論順序如何揍移，都是正確的。這是一個非常關(guān)鍵的性質(zhì)反肋。換句話說那伐，完成第1輪松弛改進后，對于任一節(jié)點u石蔗，如果s到u存在一條邊數(shù)（注意不是長度）為1的最短路徑罕邀，那么從s到u點的（某條）邊數(shù)為1最短路徑的就一定能解出來。推而廣之养距，做完第k輪松弛改進后诉探，對于任一節(jié)點u，如果從s到u存在邊數(shù)為k的最短路徑棍厌，那么這樣的一條最短路徑一定會被找出來肾胯。我們可以用數(shù)學(xué)歸納法進行證明。假設(shè)k-1輪后的情況已經(jīng)得證定铜，再假設(shè)s到某個點u有一條邊數(shù)為k的最短路徑阳液，為[s, m₁, m₂, ..., m_k-2, u]，且s與u中間不存在邊數(shù)小于k的最短路徑（D[u]還未記錄最短路徑的長度）揣炕，那么帘皿，通過反證法可知，[s, m₁, m₂, ..., m_k-2]肯定是從s到m_k-2的一條最短路徑畸陡，據(jù)前面的假設(shè)鹰溜，這條路徑的值已經(jīng)算出來了虽填，進而在第k輪處理(m_k-2, u)的時候，一定會對D[u]和P[u]的值有所改進（也就是說relax方法返回True）曹动，兩者的值都會是最終正確的解答而且不會再發(fā)生改變了斋日。綜上，前面的命題得證墓陈。

另外恶守，還有一個特別重要的引理：如果一個節(jié)點數(shù)為n的圖中沒有負權(quán)環(huán)，那么其任意兩個節(jié)點之間一定存在最短路徑贡必，且其邊數(shù)不會超過n-1兔港。這一引理從直觀上很好理解，所以這里不給出嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明仔拟。這條引理非常重要衫樊，因為它有兩個很關(guān)鍵的推論：

1. 在無負權(quán)環(huán)、節(jié)點數(shù)為n的圖中利花，遵循上面的思路科侈，我們最多只需要進行n-1輪松弛改進，就可以解決單源最短路徑問題
2. 對于節(jié)點數(shù)為n的圖炒事，如果如上進行n輪松弛改進臀栈，且最后一輪還能夠有所改進，則說明圖中必有負權(quán)環(huán)

以上就是BF的整個思路挠乳。依此可以用Python做出如下代碼實現(xiàn)：

def bellman_ford(G, s):
    D, P = {s: 0}, {s: None}
    for _ in G: # 輪數(shù)等于節(jié)點數(shù)
        improved = False
        for u in G:
            for v in G[u]:  # 任意的順序遍歷所有邊
                if relax(G, u, v, D, P):
                    improved = True
        if not improved: # 如果某輪沒有任何改進
            break        # 說明問題已經(jīng)解決挂脑，退出循環(huán)
    else:                # 否則，說明第n輪也有改進欲侮，存在負權(quán)環(huán)
        raise ValueError('negative cycle')
    return D, P

很顯然崭闲，上面算法的時間復(fù)雜度為O(nm)，其中n和m分別為節(jié)點和邊的數(shù)目威蕉。時間復(fù)雜度超過Dijkstra算法的O(mlgn)刁俭，但BF的優(yōu)勢，正如一開始所說的韧涨，在于它允許負權(quán)邊的存在而且能夠檢測到負權(quán)環(huán)的存在牍戚。