開啟主選單

求真百科

來自 搜狐網 的圖片

Dijkstra算法是專用術語。

如今,一個擁有燦爛文化的中國,帶着豐富多彩的文化元素[1]屹立在世界東方。而中華文化的典型代表之一便是漢字[2]

目錄

名詞解釋

Dijkstra算法是由荷蘭計算機科學家狄克斯特拉(Dijkstra)於1959 年提出的,因此又叫狄克斯特拉算法。是從一個頂點到其餘各頂點的最短路徑算法,解決的是有向圖中最短路徑問題

其基本原理是:每次新擴展一個距離最短的點,更新與其相鄰的點的距離。當所有邊權都為正時,由於不會存在一個距離更短的沒擴展過的點,所以這個點的距離永遠不會再被改變,因而保證了算法的正確性。不過根據這個原理,用Dijkstra求最短路的圖不能有負權邊,因為擴展到負權邊的時候會產生更短的距離,有可能就破壞了已經更新的點距離不會改變的性質。

舉例來說,如果圖中的頂點表示城市,而邊上的權重表示著城市間開車行經的距離。 Dijkstra算法可以用來找到兩個城市之間的最短路徑。

Dijkstra算法的輸入包含了一個有權重的有向圖G,以及G中的一個來源頂點S。 我們以V表示G中所有頂點的集合。 每一個圖中的邊,都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。 我們以E所有邊的集合,而邊的權重則由權重函數w: E → [0, ∞]定義。 因此,w(u,v)就是從頂點u到頂點v的非負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值,就是該路徑上所有邊的花費值總和。 已知有V中有頂點s及t,Dijkstra算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。 這個算法也可以在一個圖中,找到從一個頂點s到任何其他頂點的最短路徑。

算法描述編

這個算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。初始時,源點s的路徑長度值被賦為0(d[s]=0), 同時把所有其他頂點的路徑長度設為無窮大,即表示我們不知道任何通向這些頂點的路徑(對於V中所有頂點v除s外d[v]= ∞)。當算法結束時,d[v]中儲存的便是從s到v的最短路徑,或者如果路徑不存在的話是無窮大。 Dijstra算法的基礎操作是邊的拓展:如果存在一條從u到v的邊,那麼從s到u的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到v的路徑。這條路徑的長度是d[u]+w(u,v)。如果這個值比目前已知的d[v]的值要小,我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行到所有的d[v]都代表從s到v最短路徑的花費。這個算法經過組織因而當d[u]達到它最終的值的時候沒條邊(u,v)都只被拓展一次。

算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點,而集合Q則保留其他所有頂點。集合S初始狀態為空,而後每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d[u]值的頂點。當一個頂點u從Q中轉移到了S中,算法對每條外接邊(u,v)進行拓展。

參考文獻