貝爾曼-福特演算法（Bellman-Ford algorithm）
/ BEL-mun FORD /
戴克斯特拉聰明又快，卻脆弱：當路可以有負成本時它就垮。貝爾曼-福特用那份聰明換來蠻力的耐心。它不在處理順序上耍聰明——它就只是把每一條邊一遍又一遍地鬆弛，次數多到真正的距離不得不浮現。較慢，但它能在負權重下存活，而且額外地，它能告訴你何時根本不存在誠實的答案。
演算法很短。令 d[源點] = 0、其餘無限大。然後重複 V-1 次：把圖中每條邊各鬆弛一次。為何恰好 V-1 趟？任何最短路徑至多有 V-1 條邊（更多就會重複某頂點，而在沒有負環時重複從不划算）。第 k 趟之後，每條至多用 k 條邊的最短路徑都已完全鬆弛且正確——這是迴圈不變量，對 k 用歸納法證明：第 1 趟把所有一條邊的最短路徑做對，而之後每趟把正確路徑再延伸一條邊。所以 V-1 趟後，每條最短路徑都被找到。執行時間是 O(V * E)，因為 V-1 趟中每趟都觸及全部 E 條邊。
只要出現負權邊，貝爾曼-福特就是首選——貨幣套利圖、某些排程問題，以及作為約翰森全源演算法的第一階段。它的另一份禮物是偵測：再多跑一趟（第 V 趟）鬆弛；若還有任何邊能被鬆弛，就有一個負環可達，最短路徑問題沒有有限的答案。誠實的代價是速度——O(V*E) 遠差於戴克斯特拉接近線性的時間，所以只在你確實需要負權重或環偵測時才用貝爾曼-福特。
頂點 s、a、b，邊為 s->a (4)、a->b (-2)、s->b (5)。第 1 趟（按此順序鬆弛）：d[a]=4，接著 d[b]=min(5, 4-2)=2。經 V-1 = 2 趟後無改進，故 dist(a)=4、dist(b)=2。負邊被正確處理，這是戴克斯特拉無法保證的。
V-1 趟完整鬆弛就足夠，因為最短路徑至多 V-1 條邊；每趟把正確路徑延伸一條邊。
一趟內各邊的鬆弛順序會影響估計值下降的快慢，但不影響全部 V-1 趟後的正確性；V-1 是最壞情況的界，許多圖更早收斂（一旦某趟毫無變化即可提早停止）。