戴克斯特拉的貪婪觀點（Dijkstra as greedy）

你想知道從家鄉到其他每個城鎮的最短道路距離，道路長度非負。戴克斯特拉演算法能找到它們，而其核心是貪婪的：它反覆宣告「最近的尚未完成城鎮」已定案——永久固定其最短距離——且從不重新考慮該決定。需要的信念之躍是：最近的未定案城鎮可在無需更多資訊下被確定。

為每個頂點維護一個暫定距離，源點起始為 0、其餘為無限大。反覆執行貪婪步驟：在尚未定案的頂點中，挑暫定距離最小者，將其定案，並對其出邊做「鬆弛」——對每個鄰點，若經由此頂點較短，就降低該鄰點的暫定距離。為何「將最近的未定案頂點定案」是安全的？假設它真正的最短路徑比目前暫定值更短。那條路徑必在某處離開已定案區域，而它在外部最先到達的頂點是一個未定案頂點，其暫定距離已至少一樣大（貪婪挑的是最小者）。既然所有邊長非負，路徑其餘部分只會增加長度，故該路徑不可能更短——矛盾。這是「貪婪始終領先」式的不變量：每個已定案頂點持有其真正的最短距離。

戴克斯特拉是「正確性完全倚賴一個符號假設」的貪婪演算法的耀眼範例。一旦有負邊，論證就崩潰：稍後一條經過負邊、權重輕的繞道可能低於你已凍結的距離，故「定案最近者」的貪婪步驟變錯——你會改需貝爾曼-福特。詳細的鬆弛機制、優先佇列實作與負權處理屬於專門的最短路徑領域；這裡的重點只是：戴克斯特拉是貪婪的，以及為何「非負」正是使其貪婪正確的樞紐。