最短路徑的三角不等式性質（triangle inequality）

關於最便宜的路線有一個常識性的事實：繞路絕不會更划算。若從源點到城市 v 最便宜的方式花費某個金額，那麼先到鄰居 u、再走 u 到 v 的路，絕不會比那個最便宜的金額更少——頂多打平。停在 u 再繼續走，無法勝過真正最佳的路線，因為那個合併路線只是抵達 v 的某一種特定方式，而最短距離是所有方式中最好的。

乾淨地陳述：令 dist(x) 為從源點 s 到 x 真正的最短距離。那麼對每條權重為 w(u,v) 的邊 (u, v)，三角不等式說 dist(v) <= dist(u) + w(u,v)。理由立刻可見：右邊是到 v 某條特定路線的成本（先走到 u 的最短路線，再走那條到 v 的單邊），而 dist(v) 是到 v 所有路線中的最小值，所以它不可能超過任何一條特定路線的成本。這是整個主題的核心不變量。它精確地告訴你鬆弛何時完成：一旦對每條邊都有 d[v] <= d[u] + w(u,v)——也就是沒有任何一條邊還能再鬆弛——估計值就已收斂並等於真正的距離。

這個不等式正是所有演算法之所以正確的原因，也是最短路徑中每個終止與正確性證明的基礎。戴克斯特拉、貝爾曼-福特與 DAG 方法都靠鬆弛各邊直到三角不等式處處成立；它對所有邊成立的那一刻，d = dist。同一個不等式也證成負環偵測：若鬆弛足夠多次後仍有某條邊能被鬆弛（不等式仍被違反），則必有一個負環可達，否則估計值早該安定下來。