《啊哈！算法》第 6 章第 3 节，Bellman-Ford 算法求最短路径的 Swift 实现。
问题
已知 5 个顶点和 5 条边，求 0 点到其他顶点的最短路径。
解决
通过 n-1 次遍历所有边，找出中转至目标顶点的最短路径。
//从顶点 u[i] 到 v[i] 的权值是 w[i]
let u = [1, 0, 0, 3, 2]
let v = [2, 1, 4, 4, 3]
let w = [2, -3, 5, 2, 3]
let n = 5 //顶点数量
let m = 5 //边的数量
var inf = 99999999
//初始化 dis，表示 0 点到其他顶点的距离
var dis = [inf, inf, inf, inf, inf]
//自己到自己距离为 0
dis[0] = 0
//标记 dis 是否发生改变
var check = 0
//进行 n-1 轮“松弛”
for k in 0..<n-1 {
check = 0
for i in 0..<m { //枚举每一条边
//尝试对每一条边松弛
//源点到 v[i] 的距离与中转到达的权值比较大小
//从 u[i] 到 v[i]，也就是权值 w[i]
//源点先到 u[i] 然后再到 v[i] = dis[u[i]] + w[i]
if dis[v[i]] > dis[u[i]] + w[i] {
dis[v[i]] = dis[u[i]] + w[i]
check = 1 //数组 dis 发生变化
}
}
//dis没变化则跳出循环
if check == 0 {
break
}
}
//输出结果
for item in dis {
print("\(item)", separator: "", terminator: " ")
}
美国应用数学家 Richard Bellman 于 1958 年发表了该算法。Lester Ford, Jr. 在 1956 年也发表了该算法。此外 Edward F. Moore 在 1957 年也发表了同样的算法。
代码在 GitHub
