Dijkstra算法算是貪心思想實現的，首先把起點到所有點的距離存下來找個最短的，然后松弛一次再找出最短的，所謂的松弛操作就是，遍歷一遍看通過剛剛找到的距離最短的點作為中轉站會不會更近，如果更近了就更新距離，這樣把所有的點找遍之后就存下了起點到其他所有點的最短距離。

問題引入：

指定一個點（源點）到其余各個頂點的最短路徑，也叫做“單源最短路徑”。例如求下圖中的1號頂點到2、3、4、5、6號頂點的最短路徑。

下面我們來模擬一下：

Dijkstra算法具體步驟為：

（1）初始時，S只包含源點，即S＝，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權（若v與u有邊）或 ）（若u不是v的出邊鄰接點）。

（2）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。

（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權。

（4）重復步驟（2）和（3）直到所有頂點都包含在S中。

接下來是代碼：

已經把幾個過程都封裝成了基本模塊：