Dijkstra“單源最短路”，是指指定一個(gè)點(diǎn)（源點(diǎn)）到其余各個(gè)頂點(diǎn)的最短路徑。例如：求下圖中的1號頂點(diǎn)到其他頂點(diǎn)的最短路徑。

dijkstra.png

• 與上文中的Floyd-Warshall算法一樣。用一個(gè)二維數(shù)組來存儲該圖。
  <pre>
  let max:Int = 10000
  var map = [[0, 1, 12, max, max, max],
  [max, 0, 9, 3, max, max],
  [max, max, 0, max, 5, max],
  [max, max, 4, 0, 13, 15],
  [max, max, max, max, 0, 4],
  [max, max, max, max, max, 0]]
  </pre>

• 用一個(gè)一維數(shù)組dist來存儲1號頂點(diǎn)到其余各個(gè)頂點(diǎn)的初始路程。
  1 2 3 4 5 6
  var dist = [0, 1, 12, max, max, max]
  我們將此時(shí)dist數(shù)組中的值稱為最短路程的“估計(jì)值”。

• 先找一個(gè)離1號頂點(diǎn)最近的頂點(diǎn)，通過dist可知，2號頂點(diǎn)是當(dāng)前離1號頂點(diǎn)最近的頂點(diǎn)，選擇了2號頂點(diǎn)之后，dist[2]就已經(jīng)從“估計(jì)值”變成“確定值”，即1號頂點(diǎn)到2號頂點(diǎn)的最短路程就是當(dāng)前的distp[2]值。再來看2->3 和 2->4 這兩條邊。先計(jì)算通過2->3這條邊能否讓1號頂點(diǎn)到3號頂點(diǎn)的路程變短：比較dis[2] + map[2][3] 和dist[3]的值，dist[3] = 12,dis[2] + map[2][3] = 1 + 9 = 10,即dist[3] > dis[2] + map[2][3],dist[3] 更新為10，這個(gè)過程叫“松弛”。這便是Dijkstra算法的主要思想：通過“邊”來松弛1號頂點(diǎn)到其余各個(gè)頂點(diǎn)的路程。同理，松弛2->4 這條邊。dist[4]更新為4.對2號頂點(diǎn)所有的出邊進(jìn)行了松弛后，dist更新為：
  var dist = [0, 1, 10, 4, max, max]

• 接下來，繼續(xù)在剩下的3，4，5和6號頂點(diǎn)中，選出離1號頂點(diǎn)最近的頂點(diǎn)4號頂點(diǎn)，對4號頂點(diǎn)用剛才的方法進(jìn)行松弛。然后在剩下的頂點(diǎn)中，繼續(xù)選出離1號頂點(diǎn)最近的頂點(diǎn)，對所有的的邊進(jìn)行松弛。直到所有的頂點(diǎn)的邊都松弛完畢。
  ok，以上就是Dijkstra算法的基本步驟，總結(jié)一下：每次找到離源點(diǎn)最近的一個(gè)頂點(diǎn)，然后以該頂點(diǎn)為中心進(jìn)行擴(kuò)展，最終得到源點(diǎn)到其余所有點(diǎn)的路徑。完整代碼如下：

<pre>
let max:Int = 10000
var map = [[0, 1, 12, max, max, max],
[max, 0, 9, 3, max, max],
[max, max, 0, max, 5, max],
[max, max, 4, 0, 13, 15],
[max, max, max, max, 0, 4],
[max, max, max, max, max, 0]]

func dijkstra(map:[Array<Int>]) -> [Int] {

var book = Array.init(repeatElement(0, count: map.count))
var dist = map.first!

book[0] = 1
for i in 0..<(map.count - 1) {
    
    //取出離源點(diǎn)最近的點(diǎn)
    var min = max
    var u = 0
    
    for j in 0..<map.count {
        if (book[j] == 0) && (map[i][j] < min)  {
            min = map[i][j]
            u = j
        }
    }
    book[u] = 1
                                                                                                                                                                                                                                                                              
    //松弛所有邊
    for v in 0..<map.count {
        if map[u][v] < max {
            if dist[v] > (dist[u] + map[u][v]) {
                dist[v] = dist[u] + map[u][v]
            }
        }
    }
}

return dist

}
print(dijkstra(map: map)) //[0, 1, 8, 4, 13, 17]
</pre>