Dijkstra 演算法是一個尋找最短路徑的演算法,可以對一張沒有負權邊的有向圖找出從原點到其他所有點的最短路徑距離
假設位於台北市的你今天想從內湖高中騎車到捷運中山站附近吃拉麵,在每個路口都有幾條路任君挑選,你的 GPS 要如何找到最短路徑呢?
Google 地圖上建議的路線
其中一種方法就是列舉每條路,把每條路的距離都加起來,然後選其中一條加起來最小的路線。這種方法可以找到最短路徑,卻要花上許多時間去列舉,甚至也有可能列舉到一些不值得考慮的路線,比如說從內湖到花蓮再南迴騎回來。顯然地,有些選擇荒謬至極
因此我們會需要有效率的 Dijkstra 演算法來幫助我們解決這個問題
設一張帶權有向圖 ,此圖具備一個將邊與正整數映射的權重函數 。若有一條路徑 ,則路徑上所有邊的權重之和 。而從 到 的最短路徑,我們可以這樣描述:
權重函數 可以描述的不僅僅可以描述距離,像是時間、成本、損失…等等都可以
單源最短路徑,是指先確定起點 ,求從 到任何 的最短路徑距離
此問題可以有許多變體:
設一張帶權有向圖 ,此圖具備一個將邊與正整數映射的權重函數 。設 為從 到 的最短路徑, 滿足 ,假設從 到 的路徑 是 的子路徑,則 是從 到 的最短路徑
將 拆解成 ,使得 。我們可以使用反證法證明之。假設 不是從 到 的最短路徑,則存在一條從 到 的路徑 ,使權重 ,則 是一條從 到 的路徑,其權重 ,這與「 從 到 的最短路徑」矛盾
因此 是從 到 的最短路徑
由 的定義,設一起點 ,對於任何邊 而言,必須符合三角不等式 。在單源最短路徑的演算法中,若我們搜尋到的邊不符合三角不等式,我們就需要把它替換掉,就如同我們求最小值的技巧一樣
Dijkstra 演算法與 Bellman-Ford 演算法的精華就是這個步驟,接下來會大量使用這個性質
至於為什麼三角不等式會成立,可以很顯然看出
要找出一張圖的最短路徑,首先我們需要有個起點 ,接下來必須拿出 BFS 來探索所有節點。Dijkstra 演算法與 BFS 有許多雷同之處,可以考慮在每次準備探索一個新節點時,優顯選擇當前待拜訪名單 (queue) 中邊權之和最小的節點來拜訪並鬆弛
為了找到目前權重之和最小的節點,我們需要維護一個陣列 存取當前從 到 的最小邊權和。此資料結構必須要初始化為 、起點設為 ,這樣才能找最小值
以下圖為例,設
接下來會從 拜訪 與 ,更新 ,並優先選擇 拜訪
在從 拜訪 時,會發現可以鬆弛,所以更新使 並拜訪
接下來還有 尚未走過,走了之後會發現 已經拜訪。如此一來這張圖就探索完了,從起點 到其他節點的距離也都完成計算,可以將 回傳
以下例子的圖比較大,可以幫助我們理解整個流程
圖源: Introduction to Algorithms, Fourth Edition, p.621
Dijkstra 演算法不可使有負的邊權。我們可以由一個簡單的例子來說明
在此圖中起點為 ,根據我們的演算法,會先找到 並記錄 。接下來走到 紀錄 ,之後走到 ,因 已被拜訪,所以不會被鬆弛。最後得到 的最短路徑長為 。然而我們可以發現若從 經過 到 這條路徑可以得到的權重和為 而不是 ,此演算法得到錯誤的結果
會有這個問題是因為正整數只會越加越大,Dijkstra 就是利用此性質運作。若圖中有負邊使邊權之和變小,Dijkstra 就無法正常運作
priority_queue
來維護pair
中的兩個值反著放若 無法到達節點 ,那麼 d[v]
對於所有 ,d[v]
,且一旦 d[v]
時,就不會改變
這可以用歸納法證明之,在此就不多贅述
如果對 ,s 藉由 到 為最短路徑,且如果在鬆弛邊 之前的任何時候 d[u]
,則在鬆弛之後的任何時候也 d[u]
在演算法結束時,對於所有節點 來說,d[u]
與 相同
我們先將程式碼中的布林陣列 vis
以一個集合 替代之,對於任何節點 而言,若 vis[u]==true
則 ,否則 。程式碼的其他 vis
都以這種方式改寫
在每次 while
迴圈開始迭代時,對於所有 而言,會得到 d[v]
= ,並將 加入 當中。最終演算法會在 時結束,且對所有 ,d[v]
。我們對 while
迴圈使用歸納法證明之
d[s]
d[v]
。演算法每次從 中拿出節點 ,我們需要證明將 放入 時,d[u]
pq.top().second
所回傳的 會有最小的 值,所以 d[u]
d[y]
,根據上述特性,可以知道 d[u]
。又因為 ,在假設中,我們已經知道 d[x]
d[y]
,又 d[u]
d[y]
,結合在一起可得 d[u]
d[y]
。因此,d[u]
,根據上限性質,此值不會再改變不同的 heap 會有不同的時間複雜度
CSES Shortest Routes I (裸的)
Zerojudge a874. 14. Trace Route (裸的)
Zerojudge q100. 超能星球 (Planet) (建圖很麻煩)
Zerojudge d793. 00929 - Number Maze
Zerojudge g422. PD.紅血球的快遞任務
AtCoder Regular Contest 084 D - Small Multiple (要把每個位元之間的轉換想成是一種狀態轉換)
ShanC 程式競賽筆記
作者: ShanC
更新: 2025/3/8