Aha! Algorithms - Floyd-Warshall
2017-03-19 本文已影响0人
su3
《啊哈!算法》第 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