今天為大家分享的算法是為解決最短路徑算法的Dijkstra算法（簡稱D算法），這是一個解決從點到點之間最短路徑的問題，看下面這張圖：
這裡，我們想要得出節點a（節點1）到節點b（節點5）的最短路徑，就是怎麼走可以使得權重值的和最小，每一條邊都有一個權重。
今天我們介紹的D算法就是解決這類問題的，這是一種貪心算法，每次只取權重和最小的點，通過不斷加入節點，來更新源節點a到各個節點的最短路徑，直到所有節點遍歷完。
算法步驟：
1、定義，遍歷過的節點集合為S，集合U為其餘節點（即未遍歷）。初始時，S只包含源點v，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即:U={其餘頂點}。若v與U中頂點u有邊，則<u,v>正常有權值，若u不是v的出邊鄰接點，則<u,v>權值為∞。
注：這裡集合S、U，是為了判斷哪些節點已經遍歷過，如果U為空了，就不繼續執行。
2、從集合U中選取一個距離v最小的頂點k，把k加入到S中。
3、以k為新考慮的中間點，修改v到U中各頂點的距離；若從源點v到頂點w的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改v到w的距離值。
例子:
4、重複步驟2、3直到所有頂點都包含在S中。
上面就是D算法的處理步驟，可能大家第一次看和我一樣很迷茫，不要緊，我們結合上面這個圖，使用D算法來詳細介紹每個步驟：
1、初始化步驟
用一個一維數組DIS來表示節點1到各個節點的最短路徑（即權重），沒有連線的用∞表示。除此之外，為了防止節點重複計算，我們把節點分成兩組，一組已經遍歷的節點集合S，另一組還沒遍歷集合U。初始化的時候，節點1在集合S中。
注：節點1到自己的權重為0。
2、從集合U中獲取離節點1最近的點（參考U在數組中的最小值，是節點2），加入到集合S，並重新計算DIS數組。
（1）節點2有到節點3和4的邊，所以數組DIS的3和4位置的值可能會變動。
（2）2到3的權重為10，所以1到3的權重為17（7+10），17大於9，所以不用變動。
（3）3到4的權重為15，所以1到4的權重為22（7+15），22小於無窮，所以DIS[4]=22。（這裡數組角標大家注意下，DIS[4]表示第四個位置，起始位置為1）
3、重複步驟2，獲取U裡面距離最近的點（這裡為節點3），重新計算DIS數組。
（1）節點3這裡和4、6有邊，所以DIS的位置4、6可能需要修改值。（節點2在S中，只考慮U中沒遍歷過的節點）。
（2）3到4的權重為11，所以1到4的權重為20（9+11），小於22（DIS[4]），所以DIS[4]=20。
（3）3到6的權重為2，所以1到6的權重為11（9+2），小於14（DIS[6]），所以DIS[6]=11。
4、重複步驟2，取節點6加入S，重新計算DIS。
節點6只有到5的邊了，所以只修改DIS[6]的值。這裡節點1到節點5的權重為20（11+9），小於無窮（DIS[5]），所以DIS[5]=20。
5、繼續重複。
這次獲取到節點4，從DIS數組可以知道1到4的權重（20）已經大於等於1到5的權重（20），所以無論如何也無法從節點4取到權重更小的路徑了，所以可以捨棄（D算法是無法解決負權重問題，所以圖的權重必須為正）。
由於節點1到節點5沒有邊連接，所以權重為無窮，大於20。所以，算法的最終結果就是：
節點1到節點5的最短路徑是20，
順序是1->3->6->5。
有了算法，必須要有代碼才有說服力，這裡我用C語言實現了D算法的代碼，大家有興趣慢慢看，慢慢研究。我貼的是部分代碼，其他不重要代碼省略。
預定義變量：
數據初始化：
D算法具體邏輯方法：
運行結果：
花了大半天的時間，終於整理完這個算法了，不說了都是眼淚。希望大家能喜歡這個文章，不枉我這麼辛苦整理。
關於最短路徑的算法，還有好幾個。我下次有機會再講講，然後分析分析優點和缺點。喜歡我文章，大家可以關注留言。