迪傑斯特拉演算法
出自 MBA智库百科(https://wiki.mbalib.com/)
迪傑斯特拉演算法(Dijkstra)
目錄 |
迪傑斯特拉演算法是由荷蘭電腦科學家狄克斯特拉於1959 年提出的,因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法,解決的是有向圖中最短路徑問題。迪傑斯特拉演算法主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。
按路徑長度遞增次序產生演算法:
把頂點集合V分成兩組:
(1)S:已求出的頂點的集合(初始時只含有源點V0)
(2)V-S=T:尚未確定的頂點集合
將T中頂點按遞增的次序加入到S中,保證:
(1)從源點V0到S中其他各頂點的長度都不大於從V0到T中任何頂點的最短路徑長度
(2)每個頂點對應一個距離值
S中頂點:從V0到此頂點的長度
T中頂點:從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度
依據:可以證明V0到T中頂點Vk的,或是從V0到Vk的直接路徑的權值;或是從V0經S中頂點到Vk的路徑權值之和
(反證法可證)
求最短路徑步驟
演算法步驟如下:
G={V,E}
1. 初始時令 S={V0},T=V-S={其餘頂點},T中頂點對應的距離值
若存在<V0,Vi>,d(V0,Vi)為<V0,Vi>弧上的權值
若不存在<V0,Vi>,d(V0,Vi)為∞
2. 從T中選取一個與S中頂點有關聯邊且權值最小的頂點W,加入到S中。
3. 對其餘T中頂點的距離值進行修改:若加進W作中間頂點,從V0到Vi的距離值縮短,則修改此距離值。
重覆上述步驟2、3,直到S中包含所有頂點,即W=Vi為止。
Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法,用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法,在很多專業課程中都作為基本內容有詳細的介紹,如數據結構,圖論,運籌學等等。