Chapter 4 -- Greedy algorithms ( 3 )

發表於 分類於 ， 閱讀次數： Disqus：

Shortest Paths ( DijKstra's Algorithm )

Scenario

\(G=(V,E)\ is\ a\ directed\ graph\ and\ I(e)=lenth\ of\ edge\ e\in E,\\ where\ I(e)\geq0\ can\ be\ distance,time\ or\ cost.\) \(Find\ the\ shortest\ path\ P(v)\ from\ s\ to\ each\ other\ v\in V-\{s\},\ where\ I(P)=lenth\ of\ P=\sum_{e\in P} I(e)\) 給定一個有向圖以及每個 edge 的 "長度"( 可以是距離、花費時間、花費成本...)，試圖找出從 s 出發距離最短的路徑。

這邊比較特殊的是，這邊不預設終點。因這個演算法不單單可以找出給定起終點的最短路徑問題，也可以更廣泛的解決給定起點不限終點的最短路徑問題。

1
2
3
4
5
6
7
8
DijKstra(G,I)
// S = the set of exploded nodes
// d(u) = the shortest path distance from s to u
1. initial S = {s} and d(s)=0
2. while S ≠ V then do
       choose node v ∉ S 但存在至少一條　edge 與 S 相連
       且 d'(v) = min { d(u)+I(e) } , u ∈ S and e = (u,v) 
       S = S + {v} and  d(v)=d'(v)

Correctness

在證明正確性之前，我們先了解一下在演算法證明中的一些小技巧。之前說過，Greedy Algorithm 證明的兩個方向 : The Greedy Algorithm stays ahead 與 The exchange argument，在這個部份我們使用的是前者。

此外，在有 Loop 迴圈的演算法中，有時候我們會先試圖證明 Loop invariant property，在嘗試推出結果。所謂的 Loop invariant property 指的是在每一個迴圈中保持不變的性質。

Loop invariant : 在演算法執行過程中，對所有 \(u\in\ S\)，且 \(d(u)\) 是 \(s-u\) 的最短路徑 \(P(u)\) 的長度。

S 的迴圈過程是一次又一次的迭代添加元素，所以我們可以用歸納法來進行證明。 Step 1. : 當 \(|S|=1\)，顯然成立。 Step 2. : 假設 \(|S|=k\geq1\) 亦成立。 當 \(|S|=k+1\) : 假設在這個迴圈中我們添加的是 \(v\)，且令 \((u,v)\) 為 \(s-v\) 的路徑 \(P(v)\) 中的最後的 edge。

對其他的 \(s-v\) 路徑 \(P\) 來說，在 \(s,v\) 之間一定有一個路徑是從 \(S\) 內的 node \(x\) 指到 \(S\) 外的 node \(y\)。 從演算法可以知道 \(d(u) + I(u,v) \leq d(x) + I(x,y)+I(y,u)\) 又，\(d(u)\) 是 \(s-u\) 的最短路徑長度。 所以，對所有的 \(s-v\) 路徑來說，\(s-u-v\) 這樣的路徑一定是最短路徑。 \(\Longrightarrow d(v)=d(u) + I(u,v)\leq I(P)\)

從上面的證明可以知道，DijKstra's Algorithm 必須要在所有 edge 權重非負的條件下才能成立。

Implementation

在 DijKstra's Algorithm 中，implementation 最困難的部分就是 while loop 迴圈中的第一二行，必須配合適當的資料結構才能夠真正有效率的運行 DijKstra's Algorithm。

Min Prior Queue

Prior Queue ( 優先佇列 ) 在進行需要提取最大或最小元素的演算法中十分有用，除了 DijKstra's Algorithm 外，還有許多演算法會建議使用 Prior Queue 來配合。

以下使用 Cormen 的 "Introduction to Algorithm" 一書中的圖例來更了解整個 DijKstra's Algorithm 的 implementation :