加權圖找最短路。用優先佇列每次挑最近的、鬆弛鄰居。地圖導航就靠它。
距離估計 dist[] —— 起點 0,其餘先當無限大 ∞;過程中不斷變小(越來越準)。
優先佇列挑最近 —— 每次從還沒定案的節點裡,挑 dist 最小的出來處理(用最小堆 O(log V))。
鬆弛 relaxation —— 對它每個鄰居 v:若 dist[u] + 邊權 < dist[v],就更新 dist[v](找到更短的路)。
一出隊就定案 —— 因為權重非負,被挑出來的節點,它的最短距離不可能再更小了。
權重非負 → 繞遠路只會更長 —— 目前距離最小的那個節點,不可能透過還沒處理的(更遠的)節點再找到更短的路。
所以一出優先佇列就「鎖定」 —— 這是 Dijkstra 貪婪選擇正確性的來源。
有負權重就不成立 —— 負邊可能讓「繞遠路反而更短」,這時要用 Bellman-Ford。
BFS 是 Dijkstra 的特例 —— 所有邊權都是 1 時,優先佇列退化成普通佇列,就是 BFS。
log V。dist 陣列 + 優先佇列 + 前驅。找最短車程(每段路時間 / 距離不同),不是最少路口 —— 最少路口才是 BFS。
轉機組合裡挑總票價最低,每段航線價格不同。
從源頭往外淹,先淹到「累積成本最低」的地方,再慢慢往貴的地方推。
從 A 出發求到各點最短距離(邊上數字是權重)。每步挑「目前 d 最小、還沒定案」的節點(紫色)展開,對鄰居鬆弛(琥珀是被更新的);定案的節點變綠色。看 B 的估計怎麼從 4 變 3、D 從 6 變 4。按「下一步」。
從 heapq 版 Dijkstra、還原路徑、格子最短路,到 Bellman-Ford(負權)、最便宜航班、A* 預告、三種最短路對照。
❌ 用在有負權重的圖 —— Dijkstra 的貪婪假設被負邊破壞,會算錯。負權用 Bellman-Ford。
❌ 沒跳過過期紀錄 —— 優先佇列裡會有同一節點的舊(較大)距離,pop 到時要用 d > dist[u] 跳過。
❌ 想去「更新堆裡的舊值」 —— 用 lazy 刪除最簡單:直接 push 新距離,pop 時檢查過期就好。
❌ 把 BFS 當加權最短路 —— BFS 只算「步數」;有權重要用 Dijkstra。
把答案打到對話裡,我幫你對。