約翰森演算法（Johnson's algorithm）
/ JON-sun /
兩難在此。戴克斯特拉快卻無法處理負權重；貝爾曼-福特能處理負值卻慢。對一個帶幾條負邊的大型稀疏圖做全源，你會很想跑 V 次快速的戴克斯特拉——但你不能，就因為那些負值。約翰森演算法是巧妙的變通：它先把每條邊重新標記，使所有權重變為非負，而不改變哪些路徑最短，然後就能自由地從每個頂點跑快速的戴克斯特拉。
訣竅是一個位勢函數。新增一個全新頂點 q，用零權重的邊連到每個頂點，並從 q 跑一次貝爾曼-福特，算出 h(v)，即從 q 到每個 v 的最短距離（這也偵測任何負環）。現在重新賦權每條邊：w'(u, v) = w(u, v) + h(u) - h(v)。兩個事實使它奏效。其一，每條重賦權的邊都非負，因為 h 滿足三角不等式 h(v) <= h(u) + w(u,v)，整理後恰為 w'(u,v) >= 0。其二，重賦權只把整條路徑的成本改變 h(起點) - h(終點)，這一項只依賴端點，所以同樣的路徑仍最短——沿任一路徑的 h 項層層相消。接著在非負的 w' 上從每個源點跑戴克斯特拉，最後解除位移：真正的 dist(u, v) = （戴克斯特拉距離） - h(u) + h(v)。用二元堆積總時間為 O(V * E log V)，在稀疏圖上遠勝弗洛伊德-沃舍爾。
約翰森是含負邊的大型稀疏圖做全源最短路徑的首選——它結合了貝爾曼-福特對負值的容忍與戴克斯特拉的速度。誠實的提醒：它比弗洛伊德-沃舍爾更難實作，一次性的貝爾曼-福特階段是不可或缺的（略過它，戴克斯特拉在負值上就會出錯），而若存在負環，整個方法會正確地回報失敗，因為不存在一致的位勢 h。
邊 u->v 的 w = -2，假設從 q 跑貝爾曼-福特得 h(u) = 5、h(v) = 4。重賦權的權重為 w' = -2 + 5 - 4 = -1……但這只在三角不等式被違反時才仍為負；因為 h(v) <= h(u) + w 意指 4 <= 5 + (-2) = 3 必須成立，這個 h 不可能——真正的 h 遵守不等式並產生 w' >= 0。在有效的位勢下每個 w' 都非負，故戴克斯特拉可安全執行。
位勢 h 遵守 h(v) <= h(u) + w(u,v)，這正好就是「重賦權的邊 w' = w + h(u) - h(v) 非負」這個陳述。
重賦權保留的是哪些路徑最短，而非它們的長度——路徑成本位移了 h(起點) - h(終點)，所以你必須把那個偏移減回去才能還原真正的距離。