Dijkstra“单源最短路”，是指指定一个点（源点）到其余各个顶点的最短路径。例如：求下图中的1号顶点到其他顶点的最短路径。
与上文中的Floyd-Warshall算法一样。用一个二维数组来存储该图。
<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>用一个一维数组dist来存储1号顶点到其余各个顶点的初始路程。
1 2 3 4 5 6
var dist = [0, 1, 12, max, max, max]
我们将此时dist数组中的值称为最短路程的“估计值”。先找一个离1号顶点最近的顶点，通过dist可知，2号顶点是当前离1号顶点最近的顶点，选择了2号顶点之后，dist[2]就已经从“估计值”变成“确定值”，即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]接下来，继续在剩下的3，4，5和6号顶点中，选出离1号顶点最近的顶点4号顶点，对4号顶点用刚才的方法进行松弛。然后在剩下的顶点中，继续选出离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>
