最短路徑樹（shortest-path tree）

當你解出單源問題時，你不只得到一份距離清單——你還免費得到一個漂亮的結構。為每個頂點收集它從源點出發最便宜路線上的最後一條路。那些被選中的路串接成一棵以源點為根的樹，而這棵樹裡從根到任一頂點的唯一路徑，就是到該頂點的一條最短路徑。一棵精簡的樹一次編碼了通往各處的最佳路線。

用鬆弛留下的前驅指標來建造它：每當鬆弛邊 (u, v) 調低了 d[v]，你就記下 pred[v] = u。最後，對每個可達頂點 v（源點除外），邊 (pred[v], v) 就是它的樹邊。這些邊構成一棵樹，因為每個頂點恰有一個前驅，而沿前驅走總會無環地回到源點。從 v 沿 pred 指標走回 s 再反轉，就得到到 v 的一條最短路徑。關鍵事實是最佳子結構：最短路徑的任一子路徑本身也是最短路徑，所以單一棵樹能同時容納到每個頂點的最短路徑——共享的前綴就是樹上共享的分支。

最短路徑樹是路由真正的交付物：GPS 給你的是一條路線，而非只是一個里程數字，而那條路線正是這棵樹裡從根到頂點的路徑。一個值得指出的微妙處：這棵樹通常不唯一——當兩條路線成本打平時，不同的決勝法產生不同但都有效的樹，全都同樣最佳。也要注意這棵樹關乎從某一個源點出發的距離，與最小生成樹無關，後者最小化邊權總和且不理會任何源點；兩者解決不同的問題，且通常長得不一樣。