dijkstra是單源點最短路算法。

借圖：

?

其基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。

初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。

?

紅色部分：為什么是從V-S中取具有最短特殊路長度的頂點u？

1、dist[u]是V-S中dist[]最短的，也就是說V-S再無中間點使dist[u]更短。

轉載于:https://www.cnblogs.com/byluoluo/p/3580939.html

總結

以上是生活随笔為你收集整理的最短路径 - dijkstra的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。