Aha! Algorithms - Dijkstra

《啊哈！算法》第 6 章第 2 节，Dijkstra 算法求最短路径的 Swift 实现。

问题

已经若干顶点和路径，求某一点到其他各点的最短路径。也称为“单源最短路径”。

解决

以 u 能到达的最短顶点 u 开始考察，以 u 为起点的边，如果 u 能到达 v，那么源点 s 就能经由 u 到达 v，遍历所有边，找到最小路径。

/*
 二维矩阵表示 0～n 个地点之间的路程
 从纵向 0～n 出发到达 横向 0～n
 inf 表示无限远，无法到达
 */
var inf = 99999999
var e = [[0,     1,  12, inf, inf, inf],
         [inf,   0,   9,   3, inf, inf],
         [inf, inf,   0, inf,   5, inf],
         [inf, inf,   4,   0,  13,  15],
         [inf, inf, inf, inf,   0,   4],
         [inf, inf, inf, inf, inf,   0]]

let n = e.count

//初始化 dis，表示地点 0 到其余各个点的估算路程
var dis = e[0]

//以点 u 为起点的边 dis[u]
var u: Int = 0

//初始化 book，存放已知的最短路径集合
var book = [Int](repeatElement(0, count: n))
var min: Int

//源点到本身为 0，标记为已知
book[0] = 1

for i in 0..<n {
    min = inf
    //在所有源点能到达的顶点中找一个离源点最近的点
    for j in 0..<n {
        if book[j] == 0 && dis[j] < min{
            min = dis[j]
            u = j
        }
    }
    
    book[u] = 1
    
    //考察以 u 为起点的边，如果 u 能到达 v，那么源点 s 就能经由 u 到达 v
    //路径长度是 dis[u] + e[u][v]
    //如果这个值比初始化的 dis[v] 小，就用间接到达的距离替换 dis[v] 中的值
    for v in 0..<n {
        if e[u][v] < inf {
            if dis[v] > dis[u] + e[u][v] {
                dis[v] = dis[u] + e[u][v]
            }
        }
    }
    //遍历完所有 e[u][v]，得到最短路径
}

//输出结果
for i in 0..<n {
    print(dis[i], separator: "", terminator: " ")
}

该算法由荷兰计算机科学家 Edsger Wybe Dijkstra 于 1959 年发表。

代码在 GitHub