Aha! Algorithms - Floyd-Warshall

《啊哈！算法》第 6 章第 1 节，Floyd-Warshall 算法求最短路径的 Swift 实现。

问题

4 个城市之间有若干条单向公路，求任意两个城市之间的最短路程。也称为“多源最短路径问题”。

解决

依次计算通过城市1～4中转时的路程，与已知的最短路程比较。

/*: 二维矩阵表示地点之间的关系
 
 * 纵向表示出发点 1～n
 * 横向表示到达点 1～n
 * 坐标系 e[0][1] 表示从 1 到 2 的距离为 2，索引值先读 纵向 后读 横向
 * inf 表示无限大，表示两个点之间没有直接的边（路线）到达
 
*/
 
var inf = 99999999
var e = [[0,     2,  6,   4],
         [inf,   0,  3, inf],
         [7,   inf,  0,   1],
         [5,   inf, 12,   0]]
let n = e.count

//从 1～n 一一计算以该路线作为中转站时的最短距离
//直接到达的距离是 e[i][j]，通过地点1到达的距离是 e[i][0] + e[0][j]
//矩阵纵向和横向两次遍历，加上有n条路线就要进行n次遍历，总共 n * n * n 次循环
for k in 0..<n {
    for i in 0..<n {
        for j in 0..<n {
            if e[i][j] > e[i][k] + e[k][j] {
                e[i][j] = e[i][k] + e[k][j]
            }
        }
    }
}

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

此算法由 Robert W. Floyd 于 1962 年发表。同年 Stephan Warshall 也独立发表了这个算法。 Robert W. Floyd 在 1978 年获得图灵奖。

代码在 GitHub