Swift最短路径之Dijkstra(单源最短路)算法

Dijkstra“单源最短路”，是指指定一个点（源点）到其余各个顶点的最短路径。例如：求下图中的1号顶点到其他顶点的最短路径。

dijkstra.png

• 与上文中的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>