阿摩線上測驗
登入
阿摩線上測驗
登入
二、給定一有向圖 G=(V,E)，其邊權重皆為正數。假設目前採用 Dijkstra 演算法計算單源（single-source）最短路徑，但在實際系統中，邊權重會隨時間動態變化（例如交通路網延遲）。請回答：
(一)為何 Dijkstra 不適合在權重頻繁變動的情境下重複執行？試設計一種 “增量式更新演算法”（incremental update approach） ，能在部分邊權更 新後有效地維護最短路徑樹（SPT）。