Dijkstra's Algorithm是用來計算single-source最短路徑的演算法，
然而限制為Graph裡edge的weight不能是負值。
使用一個set S，裡面存一些node，
這些node代表已經確認、
從source到該node的最短距離值已經計算完成。
（也就是下圖中的黑點）
以及使用一個min-priority queue Q，
以每個node裡的值當做鍵值排序。
一開始除了source以外都是∞，
因此在程式碼第5行，s會最先被取出。
在第7行的for-loop中，
會更新每個與u相鄰的node的值，
而Q裡面node的排序也會跟著改變。
因為Q是min-priority queue，
所以在第5行，每次從Q取出的node，都是值最小的node，
然後在第6行把該node加入set S中。
換句話說，
每次都會取出目前值最小的node，
然後透過該node再去更新其他node與source的最短距離。
 |
| Introduction to Algorithms Fig. 24.6 |
(a)
一開始的圖，
source為s並初始化為0，其餘node皆初始化為∞。
表格中的數值，也就是node裡的值，
代表從source到該node的最短距離。
--------------
s t x y z
0 ∞ ∞ ∞ ∞
--------------
S = { }
Q = {s, t, x, y, z} （s.distance=0，其他的都是∞，假設使用字母順序排列）
(b)
此時Q裡第一個node是s，
因此由s去更新與s相連的node：t、y的值。
t = s + (s,t) = 0 + 10 = 10
y = s + (s,y) = 0 + 5 = 5
此時s已經加入set S中，
而Q裡面的排序也更新，
目前Q裡第一個node是值最小的y。
（藍色代表S裡的node，橙色代表Q裡值最小的node，也就是下次檢查此node的out edge）
--------------
s t x y z
0 10 ∞ 5 ∞
--------------
S = {s}
Q = {y, t, x, z}
(c)
從Q裡取出y，並加入S，
接著由y去更新與y相連的node：t、x、z的值。
t = y + (y,t) = 5 + 3 = 8 <-- 因為8小於上次計算結果的10，因此把t的值更新為8
x = y + (y,x) = 5 + 9 = 14
z = y + (y,z) = 5 + 2 = 7
--------------
s t x y z
0 8 14 5 7
--------------
S = {s, y}
Q = {z, t, x}
(d)
--------------
s t x y z
0 8 13 5 7
--------------
S = {s, y, z}
Q = {t, x}
(e)
--------------
s t x y z
0 8 9 5 7
--------------
S = {s, y, z, t}
Q = {x}
(f)
--------------
s t x y z
0 8 9 5 7
--------------
S = {s, y, z, t, x}
Q = { }
因為Q已經是空集合，
程式碼的第4行測試失敗，
最短路徑計算完成。
沒有留言:
張貼留言