Dijkstra“單源最短路”，是指指定一個點（源點）到其余各個頂點的最短路徑蠕蚜。例如：求下圖中的1號頂點到其他頂點的最短路徑。
與上文中的Floyd-Warshall算法一樣。用一個二維數(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>用一個一維數(shù)組dist來存儲1號頂點到其余各個頂點的初始路程肤视。
1 2 3 4 5 6
var dist = [0, 1, 12, max, max, max]
我們將此時dist數(shù)組中的值稱為最短路程的“估計值”。先找一個離1號頂點最近的頂點涉枫，通過dist可知邢滑，2號頂點是當前離1號頂點最近的頂點，選擇了2號頂點之后愿汰，dist[2]就已經(jīng)從“估計值”變成“確定值”困后，即1號頂點到2號頂點的最短路程就是當前的distp[2]值。再來看2->3 和 2->4 這兩條邊衬廷。先計算通過2->3這條邊能否讓1號頂點到3號頂點的路程變短：比較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，這個過程叫“松弛”吗跋。這便是Dijkstra算法的主要思想：通過“邊”來松弛1號頂點到其余各個頂點的路程侧戴。同理，松弛2->4 這條邊跌宛。dist[4]更新為4.對2號頂點所有的出邊進行了松弛后酗宋，dist更新為：
var dist = [0, 1, 10, 4, max, max]接下來，繼續(xù)在剩下的3疆拘，4蜕猫，5和6號頂點中，選出離1號頂點最近的頂點4號頂點哎迄，對4號頂點用剛才的方法進行松弛回右。然后在剩下的頂點中，繼續(xù)選出離1號頂點最近的頂點漱挚，對所有的的邊進行松弛翔烁。直到所有的頂點的邊都松弛完畢。
ok旨涝，以上就是Dijkstra算法的基本步驟蹬屹，總結一下：每次找到離源點最近的一個頂點，然后以該頂點為中心進行擴展颊糜，最終得到源點到其余所有點的路徑哩治。完整代碼如下：
<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) {
//取出離源點最近的點
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>
