單源最短路徑問題（single-source shortest path）

想像一張公路地圖，每條路都有一個成本——距離、過路費、行車時間。你站在某個特定城市，稱它為源點，你想找出從它到其他每一個城市最便宜的路線。不是只到一個目的地，而是一次到所有城市。這就是單源最短路徑問題。答案是每個城市對應的一個數字（抵達它的最小總成本），如果你願意，還包含達成它的路線。

精確地說：給定一個加權圖，其中從 u 到 v 的每條邊帶有權重 w(u,v)，以及一個源點 s。對每個頂點 v，定義 dist(v) 為從 s 到 v 所有路徑中邊權總和的最小值（若 v 不可達則為無限大）。輸出是所有 v 的 dist(v)。一條路徑的成本就是它各邊權重之和，所以「最短」指的是總權重最小，未必是邊數最少——三段各為 1 的繞路勝過一條權重 10 的單邊。每個正確的演算法都靠反覆改進暫定的距離估計值來運作，這個操作叫做邊鬆弛（edge relaxation），直到估計值等於真正的距離為止。

你用哪個演算法取決於權重。若所有權重非負，戴克斯特拉演算法最快。若有些權重為負（但沒有負環），則用貝爾曼-福特演算法。若圖是有向無環圖（DAG），按拓樸排序鬆弛各邊是最快的。這個問題無所不在——GPS 導航、網路封包路由、依賴成本分析——而值得記住的陷阱是：若有一個權重為負的環可達，「最短」就失去意義，因為你可以無限繞圈，把成本壓到負無限大。