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

問題引入：

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

下面我們來模擬一下：

Dijkstra算法具體步驟為：

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

（2）從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。

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

（4）重復(fù)步驟（2）和（3）直到所有頂點(diǎn)都包含在S中。

接下來是代碼：

已經(jīng)把幾個(gè)過程都封裝成了基本模塊：