戴克斯特拉演算法與非負權重的要求（Dijkstra's algorithm）
/ DYKE-struh /
想像墨水從源點沿路網向外擴散，但墨水抵達某城市時，走的是到它最便宜的路線，所以城市嚴格按離源點多遠的順序亮起——最近的先亮。戴克斯特拉演算法正是這個擴張的邊界。它反覆抓出暫定距離最小的未定案頂點，宣布該距離為最終值，並用它鬆弛其外向邊。因為它總是定案剩下最近的頂點，每個頂點的距離恰好定案一次。
具體上，把所有頂點放進以 d 為鍵的優先佇列。從 d[源點] = 0、其餘無限大開始。重複：取出 d 最小的頂點 u（這個 d[u] 現在就是它最終的最短距離），並鬆弛每條邊 (u, v)，若 d[u] + w(u,v) 較小就在佇列中調低 d[v]。為何取出的 d[u] 保證是最終值？因為所有邊權非負，任何尚未定案、通往 u 的路徑都必先經過某個其他未定案頂點 x，而 d[x] >= d[u]（u 是最小者），故繞經 x 只會加上非負權重，不可能勝過 d[u]。用二元堆積這跑 O((V + E) log V)；用費氏堆積則為 O(E + V log V)。
只要成本不可為負，戴克斯特拉就是 GPS 與網路路由的主力，而距離與時間通常正屬此類。非負的要求不是註腳——它是承重結構。一旦有負邊，「未定案中最近的頂點是最終值」的主張就崩塌：一個你已定案的頂點，稍後可能透過一條你尚未探索的負邊以更低成本抵達，而戴克斯特拉從不重訪已定案頂點，故會回傳錯誤答案。若你有負權重，請用貝爾曼-福特，或先用約翰森演算法重新賦權；別硬修戴克斯特拉再祈禱。
戴克斯特拉的陷阱：頂點 s、a、b，邊為 s->a (1)、s->b (4)、a->b (-3)。真正的 dist(b) = 1 + (-3) = -2。但戴克斯特拉在取出 b 時就以 d[b] = 4 定案它（在 s 之後、在 a 的負邊有機會幫上忙之前），鎖死 4 而錯過 -2。非負權重正是讓「定案最小值」有效的關鍵。
只要有一條負邊，戴克斯特拉就過早定案 b；非負性正是在此被打破的那個假設。
在有負權邊的圖上，戴克斯特拉是錯的——不是慢，是錯。它可能在更便宜的負邊路線被發現前就定案某頂點，且絕不重新考慮它。