《啊哈！算法》第 6 章第 1 節(jié)，F(xiàn)loyd-Warshall 算法求最短路徑的 Swift 實(shí)現(xiàn)聪廉。
問題
4 個(gè)城市之間有若干條單向公路欺嗤，求任意兩個(gè)城市之間的最短路程。也稱為“多源最短路徑問題”叨橱。
解決
依次計(jì)算通過城市1～4中轉(zhuǎn)時(shí)的路程，與已知的最短路程比較。
/*: 二維矩陣表示地點(diǎn)之間的關(guān)系
* 縱向表示出發(fā)點(diǎn) 1～n
* 橫向表示到達(dá)點(diǎn) 1～n
* 坐標(biāo)系 e[0][1] 表示從 1 到 2 的距離為 2阅羹，索引值先讀 縱向 后讀 橫向
* inf 表示無限大，表示兩個(gè)點(diǎn)之間沒有直接的邊（路線）到達(dá)
*/
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 一一計(jì)算以該路線作為中轉(zhuǎn)站時(shí)的最短距離
//直接到達(dá)的距離是 e[i][j]教寂，通過地點(diǎn)1到達(dá)的距離是 e[i][0] + e[0][j]
//矩陣縱向和橫向兩次遍歷捏鱼，加上有n條路線就要進(jìn)行n次遍歷，總共 n * n * n 次循環(huá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]
}
}
}
}
//輸出結(jié)果
for i in 0..<n {
for j in 0..<n {
print("\(e[i][j])", separator: "", terminator: " ")
}
print("\n")
}
此算法由 Robert W. Floyd 于 1962 年發(fā)表酪耕。同年 Stephan Warshall 也獨(dú)立發(fā)表了這個(gè)算法导梆。 Robert W. Floyd 在 1978 年獲得圖靈獎(jiǎng)。
代碼在 GitHub
