全球专业中文经管百科,由121,994位网友共同编写而成,共计436,007个条目

迪傑斯特拉演算法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

(重定向自Dijkstra)

迪傑斯特拉演算法(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演算法是很有代表性的最短路徑演算法,在很多專業課程中都作為基本內容有詳細的介紹,如數據結構圖論運籌學等等。

相關條目

本條目對我有幫助9
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目投訴舉報

本条目由以下用户参与贡献

LuyinT.

評論(共0條)

提示:評論內容為網友針對條目"迪傑斯特拉演算法"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

打开APP

以上内容根据网友推荐自动排序生成

下载APP

闽公网安备 35020302032707号