邊鬆弛（edge relaxation）

每個最短路徑演算法都保有一份粗略的猜測，記錄各頂點離源點多遠，並耐心地改進這些猜測。邊鬆弛就是執行改進的那個微小動作。你看著一條從 u 到 v 的邊問：「如果我走到 u 再走這條邊，會不會比我目前對抵達 v 的最佳猜測更便宜？」若是，就把對 v 的猜測調低。整個操作就這樣——一次比較，也許一次更新。

維護一個陣列 d，其中 d[v] 是目前從源點到 v 的暫定距離，初始化為 d[源點] = 0、其餘 d[v] = 無限大。要鬆弛權重為 w 的邊 (u, v)：若 d[u] + w < d[v]，就令 d[v] = d[u] + w（並記下 u 為 v 的前驅，這樣稍後能還原路線）。關鍵在於，d[v] 始終是高估——它是到 v 某條真實已知路徑的成本，絕不會小於真正的最短距離——而鬆弛只能調低它，絕不會調高。不同演算法的差別只在鬆弛各邊的順序以及何時停止；鬆弛步驟本身在所有演算法中都完全相同。例如 d[u] = 5、到 v 的邊權為 2、而 d[v] 目前是 9，鬆弛後令 d[v] = 7。

這個單一操作是構成戴克斯特拉、貝爾曼-福特與 DAG 最短路徑的原子。每個演算法的巧妙之處在於選一個盡量少鬆弛次數的順序：戴克斯特拉透過總是定案最近的未完成頂點，使每條邊只鬆弛一次；貝爾曼-福特則粗率地把每條邊鬆弛 V-1 次。鬆弛絕不會使任何 d[v] 變錯，所以多做鬆弛只是浪費卻絕不會出錯——對正確性唯一要緊的是：真正最短路徑上的每條邊最終都以正確的順序被鬆弛到。