迪克斯徹算法

迪克斯徹算法是尋找單源最短路徑的主要算法。

基本介紹

• 中文名：迪克斯徹算法
• 性質：通信信息科學類術語

套用

適用於非負權值的加權圖。

歷史

由荷蘭計算機科學家迪克斯徹（Edsger Wybe Dijkstra，1930-2002）提出。

例證

該算法保存一個頂點集S。S中的頂點是已經找到了最短路徑的頂點。開始時，將源點假設在頂點集合S。然後反覆執行以下循環，直至頂點集S包含所有的頂點為止：對於不在S中的每個頂點，考察新加入頂點集S的頂點是否有邊到達自己；如果存在，則檢查經過該頂點的這條路徑是否比原來已知的路徑要短；如果是，則更新源點到此頂點的距離和路徑；然後，從不在S的頂點中尋找一個路徑最短的頂點加入頂點集S。該算法時間複雜度為O（N）。